Non-negative Integers without Consecutive Ones LeetCode solution in C++

1
class Solution {
2
 public:
3
  int dp[31][2];
4
  vector<int> f() {
5
    vector<int> res(31, 1);
6
    dp[1][0] = 0;
7
    dp[1][1] = 1;
8
    for (int i = 2; i < 31; i++) {
9
      dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
10
      dp[i][1] = dp[i - 1][0];
11
    }
12

13
    for (int i = 1; i < 31; i++) {
14
      res[i] = res[i - 1] + dp[i][0] + dp[i][1];
15
    }
16

17
    res[1] = 2;
18
    return res;
19
  }
20

21
  int findIntegers(int n) {
22
    int res = 0;
23
    int bits = 0;
24
    int temp = n;
25
    vector<int> v;
26
    while (temp > 0) {
27
      bits++;
28
      v.push_back(temp & 1);
29
      temp = temp >> 1;
30
    }
31
    vector<int> nums = f();
32

33
    bool valid = true, isValid = true;
34

35
    for (int i = bits - 2; i >= 0; i--) {
36
      if (v[i] == 1 && v[i + 1] == 1) {
37
        res += nums[i];
38
        isValid = false;
39
        break;
40
      } else if (v[i] == 1)
41
        res += nums[i];
42
    }
43

44
    res += nums[bits - 1];
45
    return isValid == true ? res + 1 : res;
46
  }
47
};