600. Non-negative Integers without Consecutive Ones

Problem Description

Given a positive integer n, return the number of the integers in the range [0, n] whose binary representations do not contain consecutive ones.

Example 1:

Input: n = 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.

Example 2:

Input: n = 1
Output: 2

Example 3:

Input: n = 2
Output: 3

Constraints:

• 1 <= n <= 109

Python Solution

class Solution:
    def findIntegers(self, n: int) -> int:
        # Get binary representation
        binary = bin(n)[2:]
        k = len(binary)
        
        # dp[i][j] represents the number of valid integers with length i
        # and ending with digit j
        dp = [[0, 0] for _ in range(k + 1)]
        dp[1] = [1, 1]
        
        # Fill dp table
        for i in range(2, k + 1):
            dp[i][0] = dp[i-1][0] + dp[i-1][1]  # can append 0 to both endings
            dp[i][1] = dp[i-1][0]  # can only append 1 to 0 ending
        
        # Count numbers less than n
        result = 0
        prev_bit = 0
        
        for i in range(k):
            if binary[i] == '1':
                result += dp[k-i][0]  # count numbers with 0 at this position
                if prev_bit == 1:  # consecutive ones found
                    return result
                prev_bit = 1
            else:
                prev_bit = 0
                
        return result + 1  # add 1 to include n itself

Java Solution

class Solution {
    public int findIntegers(int n) {
        // Get binary length
        int k = 32 - Integer.numberOfLeadingZeros(n);
        
        // dp[i][j] represents the number of valid integers with length i
        // and ending with digit j
        int[][] dp = new int[k + 1][2];
        dp[1][0] = dp[1][1] = 1;
        
        // Fill dp table
        for (int i = 2; i <= k; i++) {
            dp[i][0] = dp[i-1][0] + dp[i-1][1];  // can append 0 to both endings
            dp[i][1] = dp[i-1][0];  // can only append 1 to 0 ending
        }
        
        // Count numbers less than n
        int result = 0;
        int prevBit = 0;
        
        for (int i = k - 1; i >= 0; i--) {
            int bit = (n >> i) & 1;
            if (bit == 1) {
                result += dp[i + 1][0];  // count numbers with 0 at this position
                if (prevBit == 1) {  // consecutive ones found
                    return result;
                }
                prevBit = 1;
            } else {
                prevBit = 0;
            }
        }
        
        return result + 1;  // add 1 to include n itself
    }
}

C++ Solution

class Solution {
public:
    int findIntegers(int n) {
        // Get binary length
        int k = 32 - __builtin_clz(n);
        
        // dp[i][j] represents the number of valid integers with length i
        // and ending with digit j
        vector> dp(k + 1, vector(2));
        dp[1][0] = dp[1][1] = 1;
        
        // Fill dp table
        for (int i = 2; i <= k; i++) {
            dp[i][0] = dp[i-1][0] + dp[i-1][1];  // can append 0 to both endings
            dp[i][1] = dp[i-1][0];  // can only append 1 to 0 ending
        }
        
        // Count numbers less than n
        int result = 0;
        int prevBit = 0;
        
        for (int i = k - 1; i >= 0; i--) {
            int bit = (n >> i) & 1;
            if (bit == 1) {
                result += dp[i + 1][0];  // count numbers with 0 at this position
                if (prevBit == 1) {  // consecutive ones found
                    return result;
                }
                prevBit = 1;
            } else {
                prevBit = 0;
            }
        }
        
        return result + 1;  // add 1 to include n itself
    }
};

JavaScript Solution

/**
 * @param {number} n
 * @return {number}
 */
var findIntegers = function(n) {
    // Get binary length
    const binary = n.toString(2);
    const k = binary.length;
    
    // dp[i][j] represents the number of valid integers with length i
    // and ending with digit j
    const dp = Array(k + 1).fill().map(() => [0, 0]);
    dp[1][0] = dp[1][1] = 1;
    
    // Fill dp table
    for (let i = 2; i <= k; i++) {
        dp[i][0] = dp[i-1][0] + dp[i-1][1];  // can append 0 to both endings
        dp[i][1] = dp[i-1][0];  // can only append 1 to 0 ending
    }
    
    // Count numbers less than n
    let result = 0;
    let prevBit = 0;
    
    for (let i = 0; i < k; i++) {
        if (binary[i] === '1') {
            result += dp[k-i][0];  // count numbers with 0 at this position
            if (prevBit === 1) {  // consecutive ones found
                return result;
            }
            prevBit = 1;
        } else {
            prevBit = 0;
        }
    }
    
    return result + 1;  // add 1 to include n itself
};

C# Solution

public class Solution {
    public int FindIntegers(int n) {
        // Get binary length
        int k = 32 - BitOperations.LeadingZeroCount((uint)n);
        
        // dp[i][j] represents the number of valid integers with length i
        // and ending with digit j
        int[,] dp = new int[k + 1, 2];
        dp[1, 0] = dp[1, 1] = 1;
        
        // Fill dp table
        for (int i = 2; i <= k; i++) {
            dp[i, 0] = dp[i-1, 0] + dp[i-1, 1];  // can append 0 to both endings
            dp[i, 1] = dp[i-1, 0];  // can only append 1 to 0 ending
        }
        
        // Count numbers less than n
        int result = 0;
        int prevBit = 0;
        
        for (int i = k - 1; i >= 0; i--) {
            int bit = (n >> i) & 1;
            if (bit == 1) {
                result += dp[i + 1, 0];  // count numbers with 0 at this position
                if (prevBit == 1) {  // consecutive ones found
                    return result;
                }
                prevBit = 1;
            } else {
                prevBit = 0;
            }
        }
        
        return result + 1;  // add 1 to include n itself
    }
}