Minimum Increment or Double Operations to Convert

Time: O(n)

Space: O(1)

Problem Overview

Start from an all-zero array.

Intuition

Start from an all-zero array. You may add 1 to a single index or double every index at once. Doubles are shared across the array, so the needed double count is governed by the largest value, while each 1-bit in every number still needs its own increment. That yields sum(popcount(arr[i])) + floor(log2(max)).

Algorithm

1Scan the array: add Integer.bitCount(a) into incs; track maxi = max(arr).
2If maxi == 0 return 0.
3Return incs + 31 - Integer.numberOfLeadingZeros(maxi) (bit length of maxi equals floor(log2(maxi))+1; the formula matches the shared-double total).

Example Walkthrough

Input: arr = [2, 3]

1. popcount(2)+popcount(3) = 1+2 = 3 increments needed across bits.
2. maxi = 3 -> floor(log2(3)) = 1 shared double.
3. Total 4. Reverse check: [2,3] -1 -> [2,2]; /2 -> [1,1]; -1,-1 -> [0,0].

Output: 4

Common Pitfalls

• Double applies to the whole array - do not sum per-element double costs.
• Guard maxi == 0; numberOfLeadingZeros(0) is 32 and would undercount/overflow the formula.
• bitCount counts increments; leading-zero math encodes the shared doubles.
• Thinking only forward simulation also works but the closed form is O(n).

Minimum Increment or Double Operations to Convert.java

Java

// Approach: Start from all zeros. Allowed moves: +1 on one index, or double
// every index. Working backwards equals: each set bit needs one increment, and
// the number of global doubles equals floor(log2(max)). Closed form:
// sum(popcount(a)) + bitLength(max) - 1 (= 31 - numberOfLeadingZeros(max) for
// max > 0). All-zero arrays need 0 ops.
// Time: O(n) Space: O(1)
class Solution {

    public int countMinOperations(int arr[]) {
        int incs = 0, maxi = 0;

        for (int a : arr) {
            incs += Integer.bitCount(a);
            maxi = Math.max(maxi, a);
        }

        if (maxi == 0) {
            return 0;
        }

        return incs + 31 - Integer.numberOfLeadingZeros(maxi);
    }
}

Was this solution helpful?