# Short O(lg(n)) java solutions, recursive & iterative

• Recursive:

``````    public int findIntegers(int num) {
// Fibonacci
int[] oneone = {1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578};
if (num == 0) return 1;

int bit = 1 << (30 - leftmost);
if ((bit & num) > 0) return oneone[32 - leftmost];
return oneone[31 - leftmost] + findIntegers(num - (1 << (31 - leftmost)));
}
``````

Iterative:

``````    public int findIntegers(int num) {
// Fibonacci
int[] oneone = {1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578};
int ans = 0;
for (int bit = 1 << 30, i = 31; i > 0; bit >>= 1, i--) {
if ((num & bit) == 0) continue;
if ((num & (bit >> 1)) != 0) {
return ans + oneone[i];
}
ans += oneone[i - 1];
}
return ans + 1;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.