The below algorithm runs in O(lgN*k) time, where k is the number of 1's in N before the first pair of consecutive 1's.

The space is O(1), not O(32) which is O(log10(N)) in fact.

The idea is simple:

For example: 1110

We count all valid numbers from 000 to 111 first, that's all valid cases below 1000,

Then we count 1000 ~ 1100's valid cases, that's the same as 00~11.

Then we count 1100 ~ 1110's valid cases, **BUT** this time it is different, because anything starting with 11XX is already invalid, so we don't need to count anymore. we have covered all valid cases.

It's certainly possible that N itself is valid (the BUT statement doesn't apply anywhere in N), like 10101, then the algorithm counting range will look like:

```
Count [0, 10000) == [0, 1111]
Count [10000, 10100) == [0, 11]
Count [10100, 10101) == [0, 0]
```

Note the last step counts toward 10101, but it doesn't include it. So you need to add 1 (N itself) before return (I got a WA in my first submission during the contest because of this ...)

As for how to count the valid numbers between [0, 111..1], you can refer to the *calc* function below. It's a simple O(1) space DP.

```
class Solution {
int calc(int len)
{
int l0 = 1, l1 = 0;
for (int i = 0; i < len; ++i)
l0 += l1, l1 = l0 - l1;
return l1 + l0;
}
public:
int findIntegers(int num) {
int sum = 0;
bool is_last_one = false;
for (int i = 31; i >= 0; i --)
if ((1 << i & num) > 0)
{
sum += calc(i);
if ((1 << i+1 & num) > 0)
return sum;
}
return sum + 1;
}
};
```

And if we take advantage of int being 32 here, we can pre-calculate all calc(len) first, make it an array, and reduce the time complexity from O(lgN*k) to O(lgN), but increase space complexity to O(lgN) too.:

```
class Solution {
public:
int findIntegers(int num) {
int calc[32] = {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};
int sum = 0;
bool is_last_one = false;
for (int i = 31; i >= 0; i --)
if ((1 << i & num) > 0)
{
sum += calc[i];
if ((1 << i+1 & num) > 0)
return sum;
}
return sum + 1;
}
};
```