denis.shin
BAN USER
Comments (2)
Reputation 0
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
static int findMissingNumber (int [] array, int startPoint, int endPoint) {
int startValue = array[startPoint];
int endValue = array[endPoint];
if (startPoint != 0 && array[startPoint] - array[startPoint -1] >= 2) {
return array[startPoint -1] + 1;
}
if (endPoint - startPoint == 1 && endValue - startValue >= 2) {
return startValue + 1;
}
if (endValue - startValue != endPoint - startPoint) {
int middleIndex = (endPoint - startPoint) / 2 + startPoint;
int result = findMissingNumber (array, startPoint, middleIndex);
if (result < 0 ) {
result = findMissingNumber (array, middleIndex +1, endPoint);
}
return result;
} else {
return -1;
}
}
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
Here is my code
Solution is if n is square of 2 then f(n) = f(n/2*2 -1) + (n - n/2)
if n is not square of 2 then f(n) = f(n&n-1) + (f(n-(n&n-1) + (n - (n&(n-1))))
n&n-1 is square of 2 which is closest but smaller than n
If you use Hashtable to track already calculated result like cache then it's gonna be faster.
- denis.shin December 03, 2015