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
7
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
4
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:
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;
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:
16
16 → 8
8 → 4
4 → 2
2 → 1
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:
10
Set bits:
1
increments = 1
Division count:
2 → 1
bits = 1
doubles = 1
Number = 3
Binary representation:
11
Set bits:
2
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.