_600.java

package com.fishercoder.solutions;

/**
 * 600. Non-negative Integers without Consecutive Ones
 *
 * Given a positive integer n, find the number of non-negative integers less than or equal to n, whose binary representations do NOT contain consecutive ones.

 Example 1:
 Input: 5
 Output: 5
 Explanation:
 Here are the non-negative integers <= 5 with their corresponding binary representations:
 0 : 0
 1 : 1
 2 : 10
 3 : 11
 4 : 100
 5 : 101
 Among them, only integer 3 disobeys the rule (two consecutive ones) and the other 5 satisfy the rule.

 Note: 1 <= n <= 109
 */
public class _600 {

    public static class DPSolution {
        /**Credit: https://leetcode.com/articles/non-negative-integers-without-consecutive-ones/#approach-3-using-bit-manipulation-accepted*/
        public int findIntegers(int num) {
            int[] f = new int[32];
            f[0] = 1;
            f[1] = 2;
            for (int i = 2; i < f.length; i++) {
                f[i] = f[i - 1] + f[i - 2];
            }
            int i = 30, sum = 0, prev_bit = 0;
            while (i >= 0) {
                if ((num & (1 << i)) != 0) {
                    sum += f[i];
                    if (prev_bit == 1) {
                        sum--;
                        break;
                    }
                    prev_bit = 1;
                } else {
                    prev_bit = 0;
                }
                i--;
            }
            return sum + 1;
        }
    }

    /**Brute force is definitely correct, but too time consuming and resulted in TLE.*/
    public int findIntegers(int num) {
        int answer = 0;
        for (int i = 0; i <= num; i++) {
            if (hasConsecutiveOnes(i)) answer++;
        }
        return answer;
    }

    private boolean hasConsecutiveOnes(int num) {
        String bin = Integer.toBinaryString(num);
        for (int i = 0; i < bin.length()-1; i++) {
            if (bin.charAt(i) == '1' && bin.charAt(i+1) == '1') return false;
        }
        return true;
    }

}