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.
1function minimumOneBitOperations(num) {
2 if (num === 0) return 0;
3 let x = 1, bit = 0;
4 while ((x << 1) <= num) {
5 x <<= 1;
6 bit++;
7 }
8 return minimumOneBitOperations(num ^ x) + (1 << bit);
9}
10
11let n = 6;
12console.log(minimumOneBitOperations(n));This JavaScript function uses recursion and bit operations to find the answer, with shifts to calculate bit positions.
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)
1using namespace std;
int minimumOneBitOperations(int num) {
int res = 0;
while (num > 0) {
res ^= num;
num >>= 1;
}
return res;
}
int main() {
int n = 6;
cout << minimumOneBitOperations(n) << endl;
return 0;
}The function performs operations iteratively, applying XOR and right shifts to effectively reach zero.