Minimum Increment or Double Operations to Convert an Array

Problem Statement

You are given an integer array arr[]. Initially, another array of the same size contains only 0s.

You can perform only two types of operations:

Increment any one element by 1.
Double all elements of the array simultaneously.

Your task is to determine the minimum number of operations required to transform the initial all-zero array into the given array.

Examples

Example 1

Input

arr = [16, 16, 16]

Output

Explanation

[0,0,0]
→ [1,1,1]      (3 increment operations)
→ [2,2,2]      (1 double)
→ [4,4,4]      (1 double)
→ [8,8,8]      (1 double)
→ [16,16,16]   (1 double)

Total = 3 + 4 = 7

Example 2

Input

arr = [2,3]

Output

Explanation

[0,0]
→ [1,1]    (2 increments)
→ [2,2]    (1 double)
→ [2,3]    (1 increment)

Total = 4

Observation

Instead of thinking from 0 → target, think in reverse:

Target → 0

Reverse the operations:

Increment becomes decrement by 1.
Double becomes divide every element by 2.

This reverse approach reveals two important observations.

Observation 1: Odd Numbers Require a Decrement

Whenever a number is odd, it could not have been obtained by doubling.

Therefore, the last operation for that number must have been an increment.

For example:

7 → 6
5 → 4
3 → 2

Every odd value requires one decrement.

The total number of such decrements equals the number of set bits (1s) in the binary representation of every number.

Example

13 = 1101

Set bits = 3

This means 13 requires exactly 3 increment operations.

Java provides this directly using:

Integer.bitCount(num);

Observation 2: Doubling Affects the Entire Array

A doubling operation affects every element simultaneously.

Therefore, we only care about the maximum number of doublings required by any element.

For example:

16

1 → 2 → 4 → 8 → 16

It requires 4 doublings.

Similarly:

8  → 3 doublings
4  → 2 doublings
2  → 1 doubling
1  → 0 doublings

The answer is simply the maximum doubling count among all elements.

Algorithm

For every element:

Count its set bits.
Count how many times it can be divided by 2 before becoming 1.
Keep the maximum division count.
Return:

Total Increments + Maximum Doublings

Complete Code

class Solution {

    public int countMinOperations(int arr[]) {
        int increments = 0;
        int doubles = 0;

        for (int num : arr) {

            // Count increment operations
            increments += Integer.bitCount(num);

            // Count required doubles
            int bits = 0;
            while (num > 1) {
                num >>= 1;
                bits++;
            }

            doubles = Math.max(doubles, bits);
        }

        return increments + doubles;
    }
}

Code Explanation

Step 1

int increments = 0;
int doubles = 0;

increments stores the total number of increment operations.
doubles stores the maximum number of doubling operations required.

Step 2

for (int num : arr)

Process every element independently.

Step 3

increments += Integer.bitCount(num);

Integer.bitCount(num) returns the number of 1s in the binary representation.

Examples:

5  → 101  → 2

10 → 1010 → 2

13 → 1101 → 3

Each set bit corresponds to one increment operation.

Step 4

int bits = 0;

while (num > 1) {
    num >>= 1;
    bits++;
}

>>= 1 divides the number by 2.

Example:

The loop runs 4 times, meaning 4 doubling operations are required.

Step 5

doubles = Math.max(doubles, bits);

Since one doubling affects the entire array, only the largest doubling requirement matters.

Example:

[4, 8, 2]

4 needs 2 doubles
8 needs 3 doubles
2 needs 1 double

Maximum = 3

Step 6

return increments + doubles;

The answer is:

Total Increment Operations
+
Maximum Double Operations

Dry Run

Input

arr = [2, 3]

Number = 2

Binary representation:

Set bits:

increments = 1

Division count:

2 → 1

bits = 1

doubles = 1

Number = 3

Binary representation:

Set bits:

increments = 3

Division count:

3 → 1

bits = 1

doubles = 1

Final result:

increments = 3
doubles = 1

Answer = 3 + 1 = 4

Why Does This Work?

Every set bit represents one increment that must have occurred at some point.
Every division by 2 in reverse corresponds to one doubling in the forward direction.
Since doubling is performed on the entire array at once, only the element requiring the most doublings determines the total number of doubling operations.

Therefore,

Answer =
Σ (set bits of every element)
+
maximum(divisions by 2 among all elements)

Complexity Analysis

Operation	Complexity
Processing each element	O(log(max(arr[i])))
Overall Time Complexity	O(n × log(max(arr[i])))
Auxiliary Space	O(1)

Each number is processed once, and dividing by 2 takes at most log₂(maxValue) iterations.

Key Takeaways

Reverse thinking often simplifies operation-based problems.
The number of set bits directly gives the required increment operations.
The maximum number of repeated divisions by 2 (equivalently, the maximum binary length minus one) determines the required doubling operations.
Since doubling affects the entire array simultaneously, only the largest doubling count contributes to the final answer.
The algorithm runs in O(n × log(maxValue)) time with O(1) extra space.

Summary

This problem can be solved efficiently by working backward from the target array to the zero array. Each set bit in a number represents a required increment operation, while the maximum number of times any element can be divided by 2 determines the required doubling operations. Combining these two observations yields an optimal solution that runs in O(n × log(maxValue)) time and uses O(1) additional space, making it suitable for large input sizes.