Minimum Operations to Reach n

Problem Overview

Starting from 0, the allowed moves are adding 1 or doubling.

Intuition

Starting from 0, the allowed moves are adding 1 or doubling. Thinking backwards from n is easier: an odd number can only come from adding 1, and an even number is best reached by doubling half of it. Each set bit of n therefore costs one addition, and each step from the top bit down costs one doubling. The answer is the number of set bits plus the bit length minus one, and both counts are single instructions in Java.

Algorithm

1If n is 0, no operations are needed.
2Count the set bits of n with Integer.bitCount.
3Find the bit length minus one as 31 minus the number of leading zeros.
4Return the sum of those two values.

Example Walkthrough

Input: n = 7

1. In binary, 7 is 111, which has three set bits and a length of three.
2. The moves are 0 to 1, double to 2, add to 3, double to 6, and add to 7.
3. That is three additions plus two doublings, for five operations.

Output: 5

Common Pitfalls

• The first move from 0 must be an addition, because doubling 0 stays at 0.
• Subtracting when n is odd and halving when it is even is the same greedy rule, but it loops once per bit.
• A power of two needs one addition and then only doublings.
• Use the built in bit functions instead of a loop to get constant time.

Minimum Operations to Reach n.java

Java

// Approach: Work backwards from n to 0. An odd number must come from a +1, so
// each set bit costs one operation, and every other step halves the number,
// so each shift down costs one. The total is the number of set bits plus the
// bit length minus one. Both are single CPU instructions in Java.
// Complexity: O(1) time, O(1) extra space.
class Solution {
    public int minOperation(int n) {
        if (n <= 0)
            return 0;
        return Integer.bitCount(n) + 31 - Integer.numberOfLeadingZeros(n);
    }
}

Was this solution helpful?