Minimum Operations to Reduce an Integer to 0

Medium Bit Manipulation Tricks to remember Original on LeetCode

Minimum Operations to Reduce an Integer to 0 is a medium bit manipulation problem solved with the tricks to remember pattern. The best approach, optimal (greedy on the two lowest bits), runs in O(log n) time and O(1) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (bfs over values) up.

Problem

You are given a positive integer n. In one operation you may add any power of two (2^i for some i >= 0) to n or subtract any power of two from it.

Return the smallest number of operations needed to make n equal to 0.

Examples

Example 1

Input
n = 27
Output
3
Why
27 = 32 - 4 - 1: add 4 (31), add 1 (32), subtract 32 (0).

Example 2

Input
n = 20
Output
2
Why
20 = 16 + 4: subtract 4, then subtract 16.

Example 3

Input
n = 1
Output
1
Why
1 is itself a power of two, so one subtraction finishes.

Constraints

  • 1 <= n <= 10^5

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (BFS over values)O(V · log V) with V = 2^18O(V)
Recursion on the lowest set bitO(2^b) with b ≈ 17 bitsO(b)
Optimal (greedy on the two lowest bits)O(log n)O(1)

1Brute force (BFS over values)

TimeO(V · log V) with V = 2^18Each of the V values is visited once and tries about 18 powers in both directions.
SpaceO(V)The distance array and the queue hold up to V values.

Treat every integer as a node and each ± power of two as an edge. A breadth-first search from n finds the fewest steps to reach 0. Values never need to go above 2^18 because n < 2^17.

  1. dist[n] = 0; push n into a queue.
  2. Pop v; for every power p = 2^0 .. 2^17, try v + p and v - p if they stay inside [0, 2^18].
  3. The first time 0 is reached, return its distance.
class Solution {
    public int minOperations(int n) {
        int limit = 1 << 18;
        int[] dist = new int[limit + 1];
        Arrays.fill(dist, -1);
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        dist[n] = 0;
        queue.add(n);
        while (!queue.isEmpty()) {
            int v = queue.poll();
            if (v == 0) return dist[v];
            for (int k = 0; k < 18; k++) {
                int p = 1 << k;
                int[] next = { v + p, v - p };
                for (int w : next) {
                    if (w >= 0 && w <= limit && dist[w] == -1) {
                        dist[w] = dist[v] + 1;
                        queue.add(w);
                    }
                }
            }
        }
        return -1;
    }
}

2Recursion on the lowest set bit

TimeO(2^b) with b ≈ 17 bitsEach call clears one more low bit and branches in two, so the recursion tree has at most about 2^b leaves.
SpaceO(b)The recursion depth is at most the number of bits plus one.

Some operation has to clear the lowest set bit low of n. Subtracting it gives n - low; adding it gives n + low, which also clears that bit and pushes a carry upward. Try both and keep the better one. A power of two needs exactly one step.

  1. If n is a power of two, return 1.
  2. low = n & -n.
  3. Return 1 + min(solve(n - low), solve(n + low)).
class Solution {
    public int minOperations(int n) {
        if ((n & (n - 1)) == 0) return 1;
        int low = n & -n;
        return 1 + Math.min(minOperations(n - low), minOperations(n + low));
    }
}

3Optimal (greedy on the two lowest bits)

TimeO(log n)Every iteration either shifts n right or is followed by a shift, and n has O(log n) bits (a carry adds at most one bit).
SpaceO(1)Only n and a counter.

Scan the bits from the bottom. A lone 1 (the bit above it is 0) is cheapest to subtract. When the two lowest bits are both 1 you are inside a run of ones, and adding 1 collapses the whole run into a single higher bit, which is never worse than subtracting each one.

  1. While n > 0:
  2. If n & 3 == 3, do n += 1 and count one operation.
  3. Else if n & 1 == 1, do n -= 1 and count one operation.
  4. Else shift n right by one (a zero bit costs nothing).
  5. Return the count.
class Solution {
    public int minOperations(int n) {
        int ops = 0;
        while (n > 0) {
            if ((n & 3) == 3) {
                n++;
                ops++;
            } else if ((n & 1) == 1) {
                n--;
                ops++;
            } else {
                n >>= 1;
            }
        }
        return ops;
    }
}

Edge cases to test

  • n is already a power of two (answer 1)
  • A long run of ones like 15 or 63: adding 1 turns the whole run into a single bit
  • Isolated ones separated by zeros, where subtracting each bit is best
  • Pattern like 0b1011: a run of two ones next to a single one

Hints

Hint 1

Each operation adds or subtracts one power of two. Think of n in binary.

Hint 2

The lowest set bit must be cleared by some operation. Either subtract it, or add it and let the carry move up.

Hint 3

If the two lowest bits are both ones, adding is never worse; if only the lowest is one, subtract it.

FAQ

What is the best time complexity for Minimum Operations to Reduce an Integer to 0?

Optimal (greedy on the two lowest bits) runs in O(log n) time and O(1) extra space. Every iteration either shifts n right or is followed by a shift, and n has O(log n) bits (a carry adds at most one bit).

Which pattern does Minimum Operations to Reduce an Integer to 0 use?

It is a bit manipulation problem that uses the tricks to remember pattern. Other problems with the same pattern: Number of 1 Bits, Set the rightmost unset bit, XOR of 1 to n Numbers.

Is there a brute force solution for Minimum Operations to Reduce an Integer to 0?

Yes. Brute force (BFS over values) takes O(V · log V) with V = 2^18 time and O(V) space. Treat every integer as a node and each ± power of two as an edge.

Which edge cases should I test for Minimum Operations to Reduce an Integer to 0?

n is already a power of two (answer 1); A long run of ones like 15 or 63: adding 1 turns the whole run into a single bit; Isolated ones separated by zeros, where subtracting each bit is best; Pattern like 0b1011: a run of two ones next to a single one.