Sponsored
Sponsored
This approach utilizes dynamic programming to count the number of non-negative integers without consecutive ones. By breaking down the problem, we can avoid redundant work by storing solutions to subproblems.
Time Complexity: O(1) since we iterate over a fixed number of bits (30 bits for int).
Space Complexity: O(1) for storing a constant size dp array.
1#include <vector>
2#include <iostream>
3using namespace std;
4
5class Solution {
6public:
7 int findIntegers(int num) {
8 vector<int> dp(31);
9 dp[0] = 1;
10 dp[1] = 2;
11 for (int i = 2; i < 31; ++i) {
12 dp[i] = dp[i - 1] + dp[i - 2];
13 }
14
15 int prev_bit = 0, result = 0;
16
17 for (int i = 29; i >= 0; --i) {
18 if ((num & (1 << i)) != 0) {
19 result += dp[i];
20 if (prev_bit == 1) {
21 return result;
22 }
23 prev_bit = 1;
24 } else {
25 prev_bit = 0;
26 }
27 }
28 return result + 1;
29 }
30};
31
32int main() {
33 Solution sol;
34 int n = 5;
35 cout << sol.findIntegers(n) << endl;
36 return 0;
37}In C++, the approach is similar to C. We use a dp array to store results for each bit level, calculate the potential valid numbers, track consecutive ones, and return the correct count of valid numbers.
In this approach, we tackle the problem recursively and use memoization to store and retrieve solutions to subproblems, thereby optimizing overlapping subproblem calculations.
Time Complexity: Generally O(log n), as the recursion iterates over each bit once.
Space Complexity: O(log n) due to the recursive call stack and memo storage.
1class Solution:
2 def __init__(self)
The Python solution mirrors the C++ solution by breaking down the integer into binary bits and evaluating recursively through depth-first search. It stores computed results in a dictionary to avoid re-calculating overlapping subproblems.