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 |
---|---|---|
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);
}
};
Java
-
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; } }
-
// 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(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