Welcome to Subscribe On Youtube

600. Non-negative Integers without Consecutive Ones

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

Solutions

  • class Solution {
        private int[] a = new int[33];
        private int[][] dp = new int[33][2];
    
        public int findIntegers(int n) {
            int len = 0;
            while (n > 0) {
                a[++len] = n & 1;
                n >>= 1;
            }
            for (var e : dp) {
                Arrays.fill(e, -1);
            }
            return dfs(len, 0, true);
        }
    
        private int dfs(int pos, int pre, boolean limit) {
            if (pos <= 0) {
                return 1;
            }
            if (!limit && dp[pos][pre] != -1) {
                return dp[pos][pre];
            }
            int up = limit ? a[pos] : 1;
            int ans = 0;
            for (int i = 0; i <= up; ++i) {
                if (!(pre == 1 && i == 1)) {
                    ans += dfs(pos - 1, i, limit && i == up);
                }
            }
            if (!limit) {
                dp[pos][pre] = ans;
            }
            return ans;
        }
    }
    
  • class Solution {
    public:
        int a[33];
        int dp[33][2];
    
        int findIntegers(int n) {
            int len = 0;
            while (n) {
                a[++len] = n & 1;
                n >>= 1;
            }
            memset(dp, -1, sizeof dp);
            return dfs(len, 0, true);
        }
    
        int dfs(int pos, int pre, bool limit) {
            if (pos <= 0) {
                return 1;
            }
            if (!limit && dp[pos][pre] != -1) {
                return dp[pos][pre];
            }
            int ans = 0;
            int up = limit ? a[pos] : 1;
            for (int i = 0; i <= up; ++i) {
                if (!(pre == 1 && i == 1)) {
                    ans += dfs(pos - 1, i, limit && i == up);
                }
            }
            if (!limit) {
                dp[pos][pre] = ans;
            }
            return ans;
        }
    };
    
  • class Solution:
        def findIntegers(self, n: int) -> int:
            @cache
            def dfs(pos, pre, limit):
                if pos <= 0:
                    return 1
                up = a[pos] if limit else 1
                ans = 0
                for i in range(up + 1):
                    if pre == 1 and i == 1:
                        continue
                    ans += dfs(pos - 1, i, limit and i == up)
                return ans
    
            a = [0] * 33
            l = 0
            while n:
                l += 1
                a[l] = n & 1
                n >>= 1
            return dfs(l, 0, True)
    
    
  • func findIntegers(n int) int {
    	a := make([]int, 33)
    	dp := make([][2]int, 33)
    	for i := range dp {
    		dp[i] = [2]int{-1, -1}
    	}
    	l := 0
    	for n > 0 {
    		l++
    		a[l] = n & 1
    		n >>= 1
    	}
    	var dfs func(int, int, bool) int
    	dfs = func(pos, pre int, limit bool) int {
    		if pos <= 0 {
    			return 1
    		}
    		if !limit && dp[pos][pre] != -1 {
    			return dp[pos][pre]
    		}
    		up := 1
    		if limit {
    			up = a[pos]
    		}
    		ans := 0
    		for i := 0; i <= up; i++ {
    			if !(pre == 1 && i == 1) {
    				ans += dfs(pos-1, i, limit && i == up)
    			}
    		}
    		if !limit {
    			dp[pos][pre] = ans
    		}
    		return ans
    	}
    	return dfs(l, 0, true)
    }
    
  • function findIntegers(n: number): number {
        const s = n.toString(2);
        const m = s.length;
        const f: number[][] = Array.from({ length: m }, () => [-1, -1]);
    
        function dfs(pos: number, pre: number, limit: boolean): number {
            if (pos >= m) {
                return 1;
            }
            if (!limit && f[pos][pre] !== -1) {
                return f[pos][pre];
            }
            const up = limit ? parseInt(s[pos]) : 1;
            let ans = 0;
            for (let i = 0; i <= up; ++i) {
                if (!(pre === 1 && i === 1)) {
                    ans += dfs(pos + 1, i, limit && i === up);
                }
            }
            if (!limit) {
                f[pos][pre] = ans;
            }
            return ans;
        }
    
        return dfs(0, 0, true);
    }
    
    

All Problems

All Solutions