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 <stdio.h>
2
3int minimumOneBitOperations(int num) {
4 if (num == 0) return 0;
5 int x = 1, bit = 0;
6 while ((x << 1) <= num) {
7 x <<= 1;
8 bit++;
9 }
10 return minimumOneBitOperations(num ^ x) + (1 << bit);
11}
12
13int main() {
14 int n = 6;
15 printf("%d\n", minimumOneBitOperations(n));
16 return 0;
17}This function computes the recursive solution. It checks the highest set bit and recurses by flipping the bit using XOR and adjusting the metric accordingly. The base case is when n is 0.
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
public class Program {
public static int MinimumOneBitOperations(int num) {
int res = 0;
while (num > 0) {
res ^= num;
num >>= 1;
}
return res;
}
public static void Main() {
int n = 6;
Console.WriteLine(MinimumOneBitOperations(n));
}
}This C# method uses iterative logic with bitwise operations to deduce the number of steps required.