C++ 4 lines DP/Fibonacci 6 ms


  • 8
    V

    If we have n bits, the number of integers without consecutive ones f(n) = f(n - 1) + f (n - 2). f(n - 1) is for the case when first bit is zero, and f(n - 2) is when then the first bit is one and second bit is zero (as we cannot have consecutive ones):

    • f(n) = "0" f(n - 1) + "10" f(n - 2).

    These are Fibonacci numbers, and we can have them in a static array for [0..31] bits.

    First, we find n, which is the position of the highest set bit in our number.

    Now, if the binary representation of our number starts with "11", then all integers will be smaller than our number, and we can just return a Fibonacci number for n bits.

    • For example, if n == 12 (binary 0b1100), highest bit at the position 4, next bit is set, so the result is 8 (fb[4]).

    If the binary representation of our number starts with "10", then all integers with n - 1 bits will be smaller than our number. So, we will grab a Fibonacci number for n - 1 bits. That's "0" + f(n - 1) case. Plus, we need to add "10.." case, so we remove the highest bit from our number and recursively call our function.

    • For example, if n == 18 (binary 0b10010), the highest bit at the position 5, next bit is unset, so taking 8 (fb[4] for 0x01111) and adding 3 (fb[2] for 0x00010).
    int findIntegers(int num) {
        static int fb[31] = { 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946,
            17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578 };
        if (num < 3) return num + 1;
        for (int bt = 29; bt >= 0; --bt) // bt should start from 30, but OJ accepts it from 29.
            if (num & (1 << bt)) return num & (1 << (bt - 1)) ? fb[bt] : fb[bt - 1] + findIntegers((num & ~(1 << bt)));
    }
    

  • 1
    J

    @votrubac How is that magic bytes array come out?


  • 0
    A

    So this problem gets multi inputs but not single input...
    so sad


  • 0
    V

    @Jery that's Fibonacci numbers, which tells us how many integers without consecutive ones we can have for n bits. I am adding more information to the description above.


  • 1
    P

    f[0] = 1 has no meaning for 0 bit. And if(num < 3) return fb[num] and fb[bt + 1] are hard to understand.
    Change the code a little bit for better meaning.
    dp[i] means the result of the number with the highest '1' on position i.

    class Solution {
    public:
        int findIntegers(int num) {
            if(num < 3) return num + 1;
            vector<int> dp(32, 0);
            dp[0] = 2, dp[1] = 3;
            for(int i = 2; i < 32; i++) dp[i] = dp[i - 1] + dp[i - 2];
            int hbit = 31;
            while((num & (1 << hbit)) == 0) hbit--;
            return (num & (1 << (hbit - 1))) ? dp[hbit] : dp[hbit - 1] + findIntegers(num & ~(1 << hbit));
        }
    };
    

  • 0
    V

    @peace good idea, updated the solution. I had zero since I wanted to get rid of "if(num < 3)" check somehow, but it started to get complicated.

    BTW, in your code you can start hbit from 30, not 31 (when you do 1 << 30, you set 31th bit).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.