Making an efficient algorithm
- by James P.
Here's my recent submission for the FB programming contest (qualifying round only requires to upload program output so source code doesn't matter). The objective is to find two squares that add up to a given value. I've left it as it is as an example. It does the job but is too slow for my liking. Here's the points that are obviously eating up time:
List of squares is being recalculated for each call of getNumOfDoubleSquares(). This could be precalculated or extended when needed.
Both squares are being checked for when it is only necessary to check for one (complements).
There might be a more efficient way than a double-nested loop to find pairs.
Other suggestions?
Besides this particular problem, what do you look for when optimizing an algorithm?
public static int getNumOfDoubleSquares( Integer target ){
int num = 0;
ArrayList<Integer> squares = new ArrayList<Integer>();
ArrayList<Integer> found = new ArrayList<Integer>();
int squareValue = 0;
for( int j=0; squareValue<=target; j++ ){
squares.add(j, squareValue);
squareValue = (int)Math.pow(j+1,2);
}
int squareSum = 0;
System.out.println( "Target=" + target );
for( int i = 0; i < squares.size(); i++ ){
int square1 = squares.get(i);
for( int j = 0; j < squares.size(); j++ ){
int square2 = squares.get(j);
squareSum = square1 + square2;
if( squareSum == target && !found.contains( square1 ) && !found.contains( square2 ) ){
found.add(square1);
found.add(square2);
System.out.println( "Found !" + square1 +"+"+ square2 +"="+ squareSum);
num++;
}
}
}
return num;
}
