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.
1class Solution {
2 public int findIntegers(int num) {
3 int[] dp = new int[31];
4 dp[0] = 1;
5 dp[1] = 2;
6 for (int i = 2; i < 31; i++) {
7 dp[i] = dp[i - 1] + dp[i - 2];
8 }
9
10 int prev_bit = 0, result = 0;
11
12 for (int i = 29; i >= 0; i--) {
13 if ((num & (1 << i)) != 0) {
14 result += dp[i];
15 if (prev_bit == 1) {
16 return result;
17 }
18 prev_bit = 1;
19 } else {
20 prev_bit = 0;
21 }
22 }
23 return result + 1;
24 }
25
26 public static void main(String[] args) {
27 Solution sol = new Solution();
28 int n = 5;
29 System.out.println(sol.findIntegers(n));
30 }
31}The Java implementation employs a dp array to precompute the number of valid integers without consecutive ones up to 31 bits in length. The main loop evaluates the bits of num to accumulate the result while checking for consecutive ones.
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.
1#include <iostream>
2#include <vector>
3#include <unordered_map>
4using namespace std;
5
6class Solution {
private:
unordered_map<int, int> memo;
int dfs(int pos, bool is_tight, bool prev_one, vector<int>& bits) {
if (pos == -1) return 1;
if (!is_tight && memo.count(pos * 2 + prev_one)) return memo[pos * 2 + prev_one];
int limit = is_tight ? bits[pos] : 1;
int res = 0;
for (int i = 0; i <= limit; ++i) {
if (prev_one && i == 1) continue;
res += dfs(pos - 1, is_tight && i == bits[pos], i == 1, bits);
}
if (!is_tight) memo[pos * 2 + prev_one] = res;
return res;
}
public:
int findIntegers(int num) {
vector<int> bits;
while (num) {
bits.push_back(num & 1);
num >>= 1;
}
return dfs(bits.size() - 1, true, false, bits);
}
};
int main() {
Solution sol;
int n = 5;
cout << sol.findIntegers(n) << endl;
return 0;
}This C++ solution implements depth-first search recursion, coupled with an unordered_map that serves as the memoization strategy. The function performs bitwise checks and combines overlaps using the memo to prevent redundant calculations.