Sponsored
Sponsored
The idea is to use a recursive function to determine the minimum number of operations needed to reduce the given number n to 0. Consider each bit change step as a recursive call, effectively exploring the tree of possibilities until we reach 0.
We need to account for the operation rules defined in the problem, particularly handling the change in the i-th bit when needed.
Time Complexity: O(log n), where n is the input size.
Space Complexity: O(log n), due to the recursion stack.
1#include <iostream>
2#include <cmath>
3using namespace std;
4
5int minimumOneBitOperations(int num) {
6 if (num == 0) return 0;
7 int x = 1, bit = 0;
8 while ((x << 1) <= num) {
9 x <<= 1;
10 bit++;
11 }
12 return minimumOneBitOperations(num ^ x) + (1 << bit);
13}
14
15int main() {
16 int n = 6;
17 cout << minimumOneBitOperations(n) << endl;
18 return 0;
19}This recursive C++ function calculates the minimum operations using bit manipulation.
This approach removes recursion and implements the bit operations iteratively. The key step involves simulating the recursive logic using a while loop and maintaining a transformation count.
Time Complexity: O(log n)
Space Complexity: O(1)
1
The Python solution handles num's bits in a loop, handling transformations using XOR operations iteratively.