lc 600. Non-negative Integers without Consecutive Ones

100100001000

One[i]:  1XXXXXXXXXXXXX

Zero[i]: 1XXXXXXXXXXXXX

Zero[i] = zero[i + 1] + one[i + 1];

One[i] = zero[i]

One[i] is the number of combination without continuous 11, with MSB 1

Zero[i] is the number of combination without continuous 11, with MSB 0

Then go over from MSB to LSB.

If at any position, it has XX00YY, let’s consider about this situation.

XX 0 1 YY      1) 

XX 1 0 YY      2)

XX 1 1 YY       3) illegal

Are the ones greater than XX00YY. But XX11YY is illegal, we will get rid of it.

Assume next one is also 00:XXX00Y

We know still it is:

XXX 1 0 Y     4) was covered by 1

XXX 0 1 Y     5)

XXX 1 1 Y     6)  illegal

We can see XXX10Y is already included in previous round. So we know, if we meet continuous XX00YY, we need to get rid of XX01YY.

Besides, we need to stop when we see 11(the two continuous 1).

public static int findIntegers(int num) {
    String str = new StringBuilder(Integer.toBinaryString(num)).toString();
    int zero[] = new int[str.length()], one[] = new int[str.length()];
    one[str.length() - 1] = zero[str.length() - 1] = 1;
    for (int i = str.length() - 2; i >= 0; i--) {
        zero[i] = zero[i + 1] + one[i + 1];
        one[i] = zero[i + 1];
    }
    int ans = one[0] + zero[0];
    for (int i = 1; i < one.length; i++) {
        if (str.charAt(i) == '1' && str.charAt(i - 1) == '1') {
            break;
        }
        if (str.charAt(i) == '0' && str.charAt(i - 1) == '0') {
            ans -= one[i];
        }
    }
    return ans;
}