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:
- 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…
- Starting from the second group, the numbers in the second half of the group all have consecutive ones, simply because they have leading
11. - 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) }