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 _theminimum number of operations to make _n equal to0.

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

Examples

Example 1

1
2
3
4
5
6
7


Input: n = 39
Output: 3
Explanation: We can do the following operations:
- Add 20 = 1 to n, so now n = 40.
- Subtract 23 = 8 from n, so now n = 32.
- Subtract 25 = 32 from n, so now n = 0.
It can be shown that 3 is the minimum number of operations we need to make n equal to 0.

Example 2

1
2
3
4
5
6
7


Input: n = 54
Output: 3
Explanation: We can do the following operations:
- Add 21 = 2 to n, so now n = 56.
- Add 23 = 8 to n, so now n = 64.
- Subtract 26 = 64 from n, so now n = 0.
So the minimum number of operations is 3.

Constraints

1 <= n <= 10^5

Solution

Method 1 – Bit Manipulation & Greedy

Intuition

The minimum number of operations is determined by how many bits need to be changed to zero, but sometimes flipping a bit can create a carry that reduces the total number of steps. The greedy approach tries both adding and subtracting powers of two at each bit position.

Approach

For each bit in n, try both adding and subtracting the nearest power of two.
Use recursion or BFS/DFS to explore both options, memoizing results to avoid recomputation.
The answer is the minimum number of steps to reach zero.
Edge case: If n is already zero, return 0.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution {
public:
    int minOperations(int n) {
        unordered_map<int, int> dp;
        function<int(int)> dfs = [&](int x) -> int {
            if (x == 0) return 0;
            if (dp.count(x)) return dp[x];
            int ans = INT_MAX;
            for (int i = 0; (1 << i) <= x * 2; ++i) {
                int p = 1 << i;
                ans = min(ans, 1 + dfs(abs(x - p)));
            }
            return dp[x] = ans;
        };
        return dfs(n);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


func minOperations(n int) int {
    dp := map[int]int{}
    var dfs func(int) int
    dfs = func(x int) int {
        if x == 0 {
            return 0
        }
        if v, ok := dp[x]; ok {
            return v
        }
        ans := 1 << 30
        for i := 0; (1<<i) <= x*2; i++ {
            p := 1 << i
            t := 1 + dfs(abs(x-p))
            if t < ans {
                ans = t
            }
        }
        dp[x] = ans
        return ans
    }
    return dfs(n)
}
func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution {
    Map<Integer, Integer> dp = new HashMap<>();
    public int minOperations(int n) {
        return dfs(n);
    }
    private int dfs(int x) {
        if (x == 0) return 0;
        if (dp.containsKey(x)) return dp.get(x);
        int ans = Integer.MAX_VALUE;
        for (int i = 0; (1 << i) <= x * 2; i++) {
            int p = 1 << i;
            ans = Math.min(ans, 1 + dfs(Math.abs(x - p)));
        }
        dp.put(x, ans);
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution {
    private val dp = mutableMapOf<Int, Int>()
    fun minOperations(n: Int): Int = dfs(n)
    private fun dfs(x: Int): Int {
        if (x == 0) return 0
        dp[x]?.let { return it }
        var ans = Int.MAX_VALUE
        var i = 0
        while ((1 shl i) <= x * 2) {
            val p = 1 shl i
            ans = minOf(ans, 1 + dfs(kotlin.math.abs(x - p)))
            i++
        }
        dp[x] = ans
        return ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution:
    def minOperations(self, n: int) -> int:
        dp: dict[int, int] = {}
        def dfs(x: int) -> int:
            if x == 0:
                return 0
            if x in dp:
                return dp[x]
            ans = float('inf')
            i = 0
            while (1 << i) <= x * 2:
                p = 1 << i
                ans = min(ans, 1 + dfs(abs(x - p)))
                i += 1
            dp[x] = ans
            return ans
        return dfs(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


use std::collections::HashMap;
impl Solution {
    pub fn min_operations(n: i32) -> i32 {
        fn dfs(x: i32, dp: &mut HashMap<i32, i32>) -> i32 {
            if x == 0 { return 0; }
            if let Some(&v) = dp.get(&x) { return v; }
            let mut ans = i32::MAX;
            let mut i = 0;
            while (1 << i) <= x * 2 {
                let p = 1 << i;
                ans = ans.min(1 + dfs((x - p).abs(), dp));
                i += 1;
            }
            dp.insert(x, ans);
            ans
        }
        let mut dp = HashMap::new();
        dfs(n, &mut dp)
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution {
    minOperations(n: number): number {
        const dp = new Map<number, number>();
        function dfs(x: number): number {
            if (x === 0) return 0;
            if (dp.has(x)) return dp.get(x)!;
            let ans = Number.MAX_SAFE_INTEGER;
            for (let i = 0; (1 << i) <= x * 2; i++) {
                const p = 1 << i;
                ans = Math.min(ans, 1 + dfs(Math.abs(x - p)));
            }
            dp.set(x, ans);
            return ans;
        }
        return dfs(n);
    }
}

Complexity

⏰ Time complexity: O(log n * log n) — For each bit position, we try both add/subtract, and memoization ensures each state is computed once. The recursion depth is up to log n.
🧺 Space complexity: O(log n) — The memoization table stores results for each possible value up to n, which is at most log n unique states.

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 – Bit Manipulation & Greedy#

Intuition#

Approach#

Code#

Complexity#