Vulkum
BAN USERI think it would be better if you used dynamic programming for the recursive version. This kind of question is the kind of question where I believe they look at this optimization thingy, as the problem is otherwise quite simple:
int[] fib = new int[n];
int fibonacci(int i){
if(i==0) return 0;
if(i==1) return 1;
if(fib[i]!=0) return fib[i]; //you have to do this assuming you have all ints=0;
//otherwise cache the result and replace the '0' with a fib value
fib[i]= fibonacci(i-1) + fibonacci(i-2);
return fib[i];
}
Classic line fill algorithm: traverse the matrix until you find a 0 (i.e. water) then start filling the "reachable" water with a different color. Do a second traversal of the matrix to see if there are any uncoloured places left.
Possible optimizations:
1) After you have found a water drop and filled in the matrix, set a boolean foundWater = true. Carry on traversing and if uncolored water found again and foundWater==true, then you can terminate.
2) Use bytes instead of ints (I was too lazy to change the solution)
public void fillPoolWithColour(int[][] map, int x, int y, int colour){
if(x>=map.length){
return;
}
if(y>=map[x].length){
return;
}
if(map[x][y]==0){
map[x][y]=colour;
}else{
//we don't want to jump out of the pool
return;
}
//move in four directions
fillPoolWithColour(map,x-1,y,colour);
fillPoolWithColour(map,x,y-1,colour);
fillPoolWithColour(map,x+1,y,colour);
fillPoolWithColour(map,x,y+1,colour);
}
public void lookForWater(int[][] map){
for(int i=0;i<map.length;i++){
for(int j=0;j<map[i].length;j++){
if(map[i][j]==0){
fillPoolWithColour(map,i,j,-1);
return;
}
}
}
}
public boolean hasPool(int[][] map){
for(int i=0;i<map.length;i++){
for(int j=0;j<map[i].length;j++){
if(map[i][j]==0){
return false;
}
}
}
return true;
}
I think you need one more step. Compute a list of gray-code values and then turn those into numbers (not their equivalent), because the problem asks for the bits of the actual numbers to be at a distance of 1, not their gray-code equivalents (i.e. 00001 and 00010, differ in 2 bits and not by 1 bit, as the problem asks, although their graycode equivalent differs in only 1 bit). So I believe one more step is required, once the gray-codes are generates is to transform them into numbers
- Vulkum February 15, 2014It is n or n-1, because, as we said in the comments below. You can always pick a pivot element which you can increment or decrement to make all elements equal apart from that pivot element. Suppose that you want to make all 0 apart from the pivot element, then what you get in fact is a sum of all elements gathered in that pivot element. Now, if that sum can be spread evenly across all the n elements, then you have n elements that can be all equal, otherwise you have n-1. However, I believe the problem is not complete, but that's what the poster says.
- Vulkum February 15, 2014
I propose this solution:
1) Check for odd palindromes starting from the second character and advancing left and right. There is no need for caching as we move one step at the time, and we print it out at every step if the palindrome condition holds.
2) Check even length palindroms starting from the second characted again but with left=i-1 and right = i.
- Vulkum February 16, 2014