Minimum Operations to Reduce an Integer to 0

Minimum Operations to Reduce an Integer to 0 - Problem

You are given a positive integer n, you can do the following operation any number of times:

Add or subtract a power of 2 from n.

Return the minimum number of operations to make n equal to 0.

A number x is power of 2 if x == 2ⁱ where i >= 0.

Input & Output

Example 1 — Medium Number

$ Input: n = 39

› Output: 3

💡 Note: 39 in binary is 100111. We can do: 39 + 1 = 40 (1 op), 40 - 8 = 32 (2 ops), 32 - 32 = 0 (3 ops). Total: 3 operations.

Example 2 — Power of 2

$ Input: n = 8

› Output: 1

💡 Note: 8 is a power of 2 (2³), so we can subtract 8 directly: 8 - 8 = 0. Only 1 operation needed.

Example 3 — Small Number

$ Input: n = 3

› Output: 2

💡 Note: 3 in binary is 11. We can do: 3 + 1 = 4 (1 op), then 4 - 4 = 0 (2 ops). Or: 3 - 2 = 1 (1 op), 1 - 1 = 0 (2 ops). Both take 2 operations.

Constraints

1 ≤ n ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input

Given positive integer n = 39

Operations

Can add or subtract powers of 2: ±1, ±2, ±4, ±8, ±16, ±32...

Goal

Find minimum operations to make n = 0

Key Takeaway

🎯 Key Insight: Use bit manipulation to handle consecutive 1s efficiently by adding rather than subtracting multiple powers of 2

Asked in

G Google 25 f Facebook 18 a Amazon 15

The key insight is to use bit manipulation: consecutive 1s in binary representation should be handled by adding the next power of 2 (carry-over) rather than subtracting each individual bit. Best approach is greedy bit manipulation with Time: O(log n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force BFS	O(2^n)	O(2^n)	Use BFS to explore all possible operations until reaching 0
Bit Manipulation (Greedy)	O(log n)	O(1)	Count set bits and handle consecutive 1s optimally
Memoization (Top-Down DP)	O(n log n)	O(n)	Recursive solution with memoization to avoid recomputing subproblems

Brute Force BFS — Algorithm Steps

Start with n in a queue
For each number, try adding/subtracting all powers of 2
Use BFS to find shortest path to 0

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin with n=39, operations=0

Explore

Try adding/subtracting powers of 2: ±1, ±2, ±4, ±8, ±16, ±32

Continue

BFS explores shortest paths first until reaching 0

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_QUEUE 100000

typedef struct {
    int val;
    int ops;
} State;

int solution(int n) {
    if (n == 0) return 0;
    
    State queue[MAX_QUEUE];
    int visited[MAX_QUEUE] = {0};
    int front = 0, rear = 0;
    
    queue[rear++] = (State){n, 0};
    if (n < MAX_QUEUE) visited[n] = 1;
    
    while (front < rear) {
        State curr = queue[front++];
        
        if (curr.val == 0) return curr.ops;
        
        int power = 1;
        while (power <= curr.val + power) {
            // Try subtracting
            int nextVal = curr.val - power;
            if (nextVal >= 0 && nextVal < MAX_QUEUE && !visited[nextVal]) {
                if (nextVal == 0) return curr.ops + 1;
                visited[nextVal] = 1;
                queue[rear++] = (State){nextVal, curr.ops + 1};
            }
            
            // Try adding
            nextVal = curr.val + power;
            if (nextVal <= 2 * n && nextVal < MAX_QUEUE && !visited[nextVal]) {
                visited[nextVal] = 1;
                queue[rear++] = (State){nextVal, curr.ops + 1};
            }
            
            power *= 2;
            if (power > 2 * n) break;
        }
    }
    
    return -1;
}

int main() {
    int n;
    scanf("%d", &n);
    int result = solution(n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

Exponential branching factor as we explore all possible operations

⚠ Quadratic Growth

Space Complexity

O(2^n)

Queue can store exponential number of states

⚠ Quadratic Space

23.5K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force BFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler