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.
1public class Main {
2 public static int minimumOneBitOperations(int num) {
3 if (num == 0) return 0;
4 int x = 1, bit = 0;
5 while ((x << 1) <= num) {
6 x <<= 1;
7 bit++;
8 }
9 return minimumOneBitOperations(num ^ x) + (1 << bit);
10 }
11
12 public static void main(String[] args) {
13 int n = 6;
14 System.out.println(minimumOneBitOperations(n));
15 }
16}This Java implementation uses recursion to compute minimum operations by leveraging bit-wise differences.
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 iterative loop continuously XORs res with current num and shifts num right, mimicking recursive pattern iteratively.