# JAVA 31 ms DP Solution with Explanation

• Here I implement two DP arrays to record the intermediate information bit by bit of the binary represented input number.

include[i]: the i bit length target number (whose binary representations do NOT contain consecutive ones) less than or equal to the first i th bit binary representation of the input number (hard to understand? I will give you the example later)

exclude[i]: the i bit length target number larger than the first i th bit binary representation of the input number.

Example: Let's assume the input number is 13(1101)
``````the initial state: include[0] = 1; exclude[0] = 0;

when i = 1, the first i th binary representation of the input number is 1
include[1] = 2 (the include numbers are 0, 1);
exclude[1] = 0;

when i = 2, the first i th binary representation of the input number is 01
include[2] = 2 (the include numbers are 00, 01);
exclude[2] = 1 (the exclude number is 10);

when i = 3, the first i th binary representation of the input number is 101
include[3] = 4 (the include numbers are 000, 001, 010, 100, 101);
exclude[3] = 0;

when i = 4, the first i th binary representation of the input number is 1101
include[4] = 8 (the include numbers are 0000, 0001, 0010, 0100, 0101, 1000, 1001, 1010);
exclude[4] = 0;
``````

In conclusion: the recursive formula is as followed:

``````// Here the flag implys whether the i - 1 th bit of the input number is 0 or not,
// if the i - 1 th bit is '0' flag = true; else flag = false;
if((num & 1) == 1){
include[i] = (exclude[i - 1] + include[i - 1]) /*(consider the i th bit of the include number is '0')*/  + (flag ? include[i - 1] : include[i - 2] + exclude[i - 2])/*(consider the i th bit of the include number is '1')*/;
exclude[i] = flag ? exclude[i - 2] : 0; // consider the i th bit of the exclude number must be '1', as a result the i - 1 th bit of the exclude number must be '0'
flag = false;
}
else{
include[i] = include[i - 1]; // consider i th bit of the include number is '0'
exclude[i] = exclude[i - 1]  /* consider the i th bit of the exclude number is '0' */+ (include[i - 2] + exclude[i - 2]) /* consider the i th bit of the exclude number is '1'*/;
flag = true;
}
``````

Now the full code is pasted:

``````public class Solution {
public int findIntegers(int num) {
if(num < 3){
return num + 1;
}

int len = 1;
int tmp = num;
// get the bit length of the input number
while(tmp / 2 > 0){
len++;
tmp /= 2;
}

int[] include = new int[len + 1];
int[] exclude = new int[len + 1];
boolean flag;

// initial state
include[0] = 1;
exclude[0] = 0;

if((num & 1) == 1){
include[1] = 2;
exclude[1] = 0;
flag = false;
}
else{
include[1] = 1;
exclude[1] = 1;
flag = true;
}

for(int i = 2; i <= len; i++){
num >>>= 1;
if((num & 1) == 1){
include[i] = exclude[i - 1] + include[i - 1] + (flag ? include[i - 1] : include[i - 2] + exclude[i - 2]);
exclude[i] = flag ? exclude[i - 2] : 0;
flag = false;
}

else{
include[i] = include[i - 1];
exclude[i] = exclude[i - 1] + include[i - 2] + exclude[i - 2];

flag = true;
}
}

return include[len];
}
}
``````

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