Участник:Gerakir/Leet Coding/Non-negative Integers without Consecutive Ones

Материал из DISCOPAL
Перейти к: навигация, поиск

600. Non-negative Integers without Consecutive Ones

class Solution {
public:
    int findIntegers(int num) 
    {        
        if (num==0)
            return 1;
        if (num==1)
            return 2;
        int f[32];
        f[0] = 1;
        f[1] = 2;
        int i;
        for (i = 2; i < 32; i++)
            f[i] = f[i-1] + f[i-2];
        int a = 0;
        int prev = 0;
        for (i = 30; i >= 0; i--) {
            if (num & (1<<i)) {
                a += f[i];
                if (prev == 1)
                    return a;
                prev = 1;
            } else
                prev = 0;
        }    
        return a+1;
    }
};