Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/600.html

600. Non-negative Integers without Consecutive Ones (Hard)

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

Companies:
Pocket Gems

Related Topics:
Dynamic Programming

Solution 1.

Let f(n) be the numbers less than or equal to n whose binary representations DO contain consecutive ones.

x | binary(x) | has consecutive ones

Welcome to Subscribe On Youtube

|—|— 0 | 0 | 1 | 1 | 2 | 10 | 3 | 11 | 1 4 | 100 | 5 | 101 | 6 | 110 | 1 7 | 111 | 1 8 | 1000 | 9 | 1001 | 10 | 1010 | 11 | 1011 | 1 12 | 1100 | 1 13 | 1101 | 1 14 | 1110 | 1 15 | 1111 | 1 16 | 10000 |

We can find pattern in this way:

  1. We separate the table rows according to count of bits. So 0~1 is the first group, 2~3 is the second group, 4~7 is the third group, 8~15 is the forth group…
  2. Starting from the second group, the numbers in the second half of the group all have consecutive ones, simply because they have leading 11.
  3. For the numbers in the first half of the groups, the pattern is the same after removing the leading 10.
    Take 14 as example which is in group 8~15, it’s in the second half, so 12~14 all have consecutive ones. And 8~11 has the same pattern as 0~3.

So we can get this equation:

let k = floor(log2(n))
let p = 2^k
f(n) = f(p-1) +
       { f(n-p)                        if n-(p-1)<= p/2
       { n-(p-1)-p/2 + f(p/2-1)        if n-(p-1)>p/2
// OJ: https://leetcode.com/problems/non-negative-integers-without-consecutive-ones/
// Time: O(logN)
// Space: O(logN)
class Solution {
private:
    unordered_map<int, int> m;
    int find(int num) {
        if (num < 2) return 0;
        if (m.find(num) != m.end()) return m[num];
        int k = log2(num), p = pow(2, k);
        int ans = find(p - 1);
        if (num > p / 2 * 3 - 1) ans += num - p / 2 * 3 + 1 + find(p / 2 - 1);
        else ans += find(num - p);
        return m[num] = ans;
    }
public:
    int findIntegers(int num) {
        return num + 1 - find(num);
    }
};
  • class Solution {
        public int findIntegers(int num) {
            if (num <= 2)
                return num + 1;
            int bits = (int) (Math.log(num) / Math.log(2));
            int counts = 2;
            int zeros = 0, ones = 1;
            for (int i = 2; i <= bits; i++) {
                int newZeros = zeros + ones;
                ones = zeros;
                zeros = newZeros;
                counts += zeros;
                counts += ones;
            }
            int zerosUnrestricted = 0, zerosRestricted = 0, onesUnrestricted = 0, onesRestricted = 1;
            for (int i = 1; i <= bits; i++) {
                int curBit = (num >> bits - i) & 1;
                if (curBit == 0) {
                    int curZerosUnrestricted = zerosUnrestricted + onesUnrestricted;
                    int curZerosRestricted = zerosRestricted + onesRestricted;
                    int curOnesUnrestricted = zerosUnrestricted;
                    int curOnesRestricted = 0;
                    zerosUnrestricted = curZerosUnrestricted;
                    zerosRestricted = curZerosRestricted;
                    onesUnrestricted = curOnesUnrestricted;
                    onesRestricted = curOnesRestricted;
                } else {
                    int curZerosUnrestricted = zerosUnrestricted + zerosRestricted + onesUnrestricted + onesRestricted;
                    int curZerosRestricted = 0;
                    int curOnesUnrestricted = zerosUnrestricted;
                    int curOnesRestricted = zerosRestricted;
                    zerosUnrestricted = curZerosUnrestricted;
                    zerosRestricted = curZerosRestricted;
                    onesUnrestricted = curOnesUnrestricted;
                    onesRestricted = curOnesRestricted;
                }
            }
            counts += zerosUnrestricted + zerosRestricted + onesUnrestricted + onesRestricted;
            return counts;
        }
    }
    
    ############
    
    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;
        }
    }
    
  • // OJ: https://leetcode.com/problems/non-negative-integers-without-consecutive-ones/
    // Time: O(logN)
    // Space: O(logN)
    class Solution {
    private:
        unordered_map<int, int> m;
        int find(int num) {
            if (num < 2) return 0;
            if (m.find(num) != m.end()) return m[num];
            int k = log2(num), p = pow(2, k);
            int ans = find(p - 1);
            if (num > p / 2 * 3 - 1) ans += num - p / 2 * 3 + 1 + find(p / 2 - 1);
            else ans += find(num - p);
            return m[num] = ans;
        }
    public:
        int findIntegers(int num) {
            return num + 1 - find(num);
        }
    };
    
  • 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)
    
    ############
    
    class Solution(object):
      def findIntegers(self, num):
        """
        :type num: int
        :rtype: int
        """
        n = bin(num)[2:][::-1]  # removes "0b"
        length = len(n)
        A = [1 for _ in range(length)]  # ends with 0
        B = [1 for _ in range(length)]  # ends with 1
    
        for i in range(1, len(n)):
          A[i] = A[i - 1] + B[i - 1]
          B[i] = A[i - 1]
        ans = A[-1] + B[-1]
        for i in range(length - 2, -1, -1):
          if n[i:i + 2] == "11":
            break
          if n[i:i + 2] == "00":
            ans -= B[i]
        return ans
    
    
  • 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)
    }
    

All Problems

All Solutions