600. Non-negative Integers without Consecutive Ones

Problem statement:

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 <= 10^9

Solution: DP

This is the last question of leetcode weekly contest 34. It is a DP and definitely is a hard problem. But, the DP formula is not difficult to figure it out. What we need to be careful is there is one requirement in the description: less than or equal to n. After we get the answer, we still need to do one more step.

Generally, this problem can be divided into several steps:

(1) Convert the original n into a binary representation string. Get the size of string to allocate memory for DP array.

(2) Do DP, like 198. House Robber, we should define two DP arrays:

dp0[i]: the number of integers when current bit set to 0
dp1[i]: the number of integers when current bit set to 1

(3) Any integer can not contain any consecutive ones.

dp0[i] = dp1[i - 1] + dp0[i - 1]
dp1[i] = dp0[i - 1]

(4) And do the last processing to find the integers which are less than or equal to n.

First, we only do the subtraction for the highest effective bit as the problem requires the number of integers is less than or equal to n.
Second. When there are two consecutive ones, the rest integers are less than it, stop!
Third, if we met 01, according to the DP formula, the number of qualified integers for first 0:

dp0[i] = dp0[i - 1] + dp1[i - 1]

both '00' and '01' are less than or equal to 01. The same for 10.

Finally, for 00, the number of qualified integers for first 0 should be '00' and '01', but '01' is greater than '00', we should subtract it.

Time complexity is O(k), k is the bit count of n.

class Solution {
public:
    int findIntegers(int num) {
        string str_num;
        while(num){
            str_num.push_back(num % 2 + '0');
            num /= 2;
        }
        int size = str_num.size();
        vector<int> dp0(size, 0);
        vector<int> dp1(size, 0);
        dp0[0] = 1;
        dp1[0] = 1;
        for(int i = 1; i < size; i++){
            dp0[i] = dp0[i - 1] + dp1[i - 1];
            dp1[i] = dp0[i - 1];
        }
        int cnt = dp0[size - 1] + dp1[size - 1];
        for (int i = size - 2; i >= 0; i--) {
            if (str_num[i] == '1' && str_num[i + 1] == '1') {
                break;
            }
            if (str_num[i] == '0' && str_num[i + 1] == '0') {
                cnt -= dp1[i];
            }
        }
        return cnt;
    }
};

600. Non-negative Integers without Consecutive Ones

推荐阅读