# Java O(1) time O(1) space DP Solution

• Build a tree to consider all possible number.

Let 1.and 0 for each bit be tree node

compress to 4 possible result for each bit:

1. all bit before cur is less than num and no continues 1 and cur bit is at one.
2. all bit before cur is less than num and no continues 1 and cur bit is at zero.
3. cur and prev bit is equal to num.
4. larger than num or has contiunes '1'.

then run through the tree.

``````public class Solution {
public int findIntegers(int num) {
//one:all bit before cur is less than num and no continues 1 and cur bit is at one;
//zero:all bit before cur is less than num and no continues 1 and cur bit is at zero;
int one=0,zero=0,temp;
boolean isNum=true;
for(int i=31;i>=0;i--){
temp=zero;
zero+=one;
one=temp;
if(isNum&&((num>>i)&1)==1){
zero+=1;
}
if(((num>>i)&1)==1&&((num>>i+1)&1)==1){
isNum=false;
}

}
return one+zero+(isNum?1:0);
}
}
``````

• li hai le wo de ge

• Bravo my borther

• superb !!!

Here is a python version:

``````class Solution(object):
def findIntegers(self, num):
"""
:type num: int
:rtype: int
"""
end0, end1 = 0, 0
prevbit = 0
for i in reversed(range(num.bit_length())):
end0, end1 = end0+end1, end0
currbit = (num>>i) & 1
end0 += 1
if currbit and prevbit:
prevbit = currbit
return end0 + end1 + no_adj_1s
``````

• Brilliant and concise solution! Let's push it to the top of all solutions :)

It took me a while to figure it out, so I added some comments in the code below. To better illustrate the idea of this solution, we can check this example:

num = (10110)2

prefix = 1
smallerPrefixEnding0 = 1, it consists of candidates {0}
smallerPrefixEnding1 = 0,
isPrefixValid = true, it consists of candidates {1}

prefix = 10
smallerPrefixEnding0 = 1, it consists of candidates {00}
smallerPrefixEnding1 = 1, it consists of candidates {01}
isPrefixValid = true, it consists of candidates {10}

prefix = 101
smallerPrefixEnding0 = 3, it consists of candidates {000,010,100}
smallerPrefixEnding1 = 1, it consists of candidates {001}
isPrefixValid = true, it consists of candidates {101}

prefix = 1011
smallerPrefixEnding0 = 5, it consists of candidates {0000,0100,1000,0010,1010}
smallerPrefixEnding1 = 3, it consists of candidates {0001,0101,1001}
isPrefixValid = false, it consists of candidates {}

prefix = 10110
smallerPrefixEnding0 = 8, it consists of candidates {00000,01000,10000,00100,10100,00010,01010,10010}
smallerPrefixEnding1 = 5, it consists of candidates {00001,01001,10001,00101,10101}
isPrefixValid = false, it consists of candidates {}

At the end, we return 8 + 5 = 13.

``````public class Solution {
public int findIntegers(int num) {
char[] str = Integer.toBinaryString(num).toCharArray();
int len = str.length;
// smallerPrefixEnding0 = num of even valid integers (binary representation ending in 0) smaller than current prefix
// smallerPrefixEnding1 = num of odd  valid integers (binary representation ending in 1) smaller than current prefix
int smallerPrefixEnding0 = 0, smallerPrefixEnding1 = 0;
// if current prefix is a valid integer
boolean isPrefixValid = true;
for (int i = 0; i < len; i++) {
int tmp = smallerPrefixEnding0 + smallerPrefixEnding1;
smallerPrefixEnding1 = smallerPrefixEnding0;
smallerPrefixEnding0 = tmp;
if (isPrefixValid) { // current prefix is still valid, keep adding new candidates
if (str[i] == '1') {
smallerPrefixEnding0++; // str[0...i-1] + '0' is smaller than str[0...i], ending in 0;
if (i > 0 && str[i - 1] == '1') { // two consecutive '1'
isPrefixValid = false;
}
}
}
//System.out.println(smallerPrefixEnding0 + " " + smallerPrefixEnding1 + " " + isPrefixValid);
}
return smallerPrefixEnding0 + smallerPrefixEnding1 + (isPrefixValid ? 1 : 0);
}
}
``````

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