Leetcode.com problem: "Non-Negative Integers Without Consecutive Ones"
James S. Plank
Sat May 28 04:15:42 PM EDT 2022
In cast Leetcode's servers are down
You have a procedure that takes an int and returns an int. Suppose
the input is n. Count how many integers there are that are
≥ 0 and ≤ n and do not have two consecutive one bits in their
binary representations. Max n is 109.
Examples
n answer
0 | 1
1 | 2
2 | 3
3 | 3
4 | 4
5 | 5
6 | 5
7 | 5
8 | 6
9 | 7
Hints
I did this one twice. My first solution was plenty fast, but pretty slow
in leetcode land (only faster than 5%). So I did a second, faster
solution. I'll talk about both.
Solution 0 -- Enumerate, so you have correct solutions
That was my first solution. I knew it would be too slow, but it
gave me answers for my other solutions. Here you go -- cut and paste
it if you want to test yourself:
int dumb(int n)
{
bool last;
int i, j, ans;
printf("dumb(%d)\n", n);
ans = 0;
for (i = 0; i <= n; i++) {
last = false;
for (j = i; j > 0; j>>=1) {
if (j&1) {
if (last) {
j = -1;
} else {
last = true;
}
} else last = false;
}
if (j == 0) ans++;
}
return ans;
}
Solution 1 -- Dynamic programming
If you know me at all, you know that I don't try to be too clever math-wise
to solve problems like this. So I don't even bother with trying for a
closed-form solution. Instead, I go straight to dynamic programming.
The key here is to spot the recursion. Here's what I did:
- I put two base cases -- 0 and 1. Then, I recognized that when
n is a power of two, the answer is 1 + dp(n-1). This
is nice, because it reduces the binary digits of n.
I tested this by using dumb() above as my catch-all solution,
and tested powers of two.
- Next, I made the realization that if the first two binary digits
are ones, then change n to be a smaller number that doesn't
start with ones. Specifically, if the binary representation
of n is:
Then I can replace n with:
You may want to think about that for a while to convince yourself that it's
true.
- So, now I can assume that n starts with "10". For example,
suppose that n is:
Then:
dp(n) = dp(1000000) + dp(abcde) - 1 |
Why -1? Well, zero is counted twice. Work through some examples to convince
yourself -- try dp(5), dp(9), dp(11). See how that goes?
Code it up and memoize and you're done. The cache is really small (under 100
when n is 9 decimal digits).
Solution 2 -- Making it faster and removing recursion
To make it faster, I pretty much made use of the same observations,
but took them a step further. Let a(n) be the answer for n.
- Obvservation 1: If n does not have two consecutive one bits,
then for each bit i of n that is set, sum up a(2i)-1. The answer is that sum, plus one.
Example: suppose n is 9. Then the answer is a(8)-1 + a(1)-1 + 1,
which is (6-1)+(2-1)+1 = 7.
- Obvservation 2: Suppose n is a power of two. In binary,
n is a 1 followed by w zeros. Then a(n) = a(m) + 1,
where m is a binary number with w-1 digits, whose first digit
is 1, and whose digits then alternate 0 and 1.
For example, suppose n is 100000 (binary). Then a(n) = a(10101)+1.
These two observations let you build a vector b, where b[i]
is a(2i)..
- Obvservation 3: Now, suppose n may be viewed as the concatenation
of three numbers: x1y, where x has no consecutive ones, and
ends with a one and y has w digits. Then, you can replace
n with x0z, where z is a w-digit number of
alternating ones and zeros.
For example, let n be 100110110. We can set x to 1001 and
y to 0110. With this observation, a(100110110) equals
a(100101010). Since this number has no consecutive 1's, you can
calculate a() directly from observation 1, using the vector b.
This took my solution from 30ms to 7ms. That was still slow compared to
other solutions, but I don't really care at this point. It's fast enough
for me to go on with the rest of my day...