Minimum Numbers of Function Calls to Make Target Array
MedPrompt
You are given an integer array nums. You have an integer array arr of the same length with all values set to 0 initially. You also have the following modify function:
You want to use the modify function to convert arr to nums using the minimum number of calls.
Return the minimum number of function calls to make nums from arr.
The test cases are generated so that the answer fits in a 32-bit signed integer.
Example 1:
Input: nums = [1,5]
Output: 5
Explanation: Increment by 1 (second element): [0, 0] to get [0, 1] (1 operation).
Double all the elements: [0, 1] -> [0, 2] -> [0, 4] (2 operations).
Increment by 1 (both elements) [0, 4] -> [1, 4] -> [1, 5] (2 operations).
Total of operations: 1 + 2 + 2 = 5.Example 2:
Input: nums = [2,2]
Output: 3
Explanation: Increment by 1 (both elements) [0, 0] -> [0, 1] -> [1, 1] (2 operations).
Double all the elements: [1, 1] -> [2, 2] (1 operation).
Total of operations: 2 + 1 = 3.Example 3:
Input: nums = [4,2,5]
Output: 6
Explanation: (initial)[0,0,0] -> [1,0,0] -> [1,0,1] -> [2,0,2] -> [2,1,2] -> [4,2,4] -> [4,2,5](nums).
Constraints:
1 <= nums.length <= 1050 <= nums[i] <= 109
Approaches
2 approaches with complexity analysis and trade-offs.
This approach simulates the process in reverse. Instead of building the target nums array from zeros, we work backward from nums to an all-zero array. The inverse operations are decrementing a single element (the reverse of an increment) and halving every element (the reverse of a double). The core logic is that we can only perform the "halve" operation if all numbers in the array are even. If any number is odd, we are forced to decrement it first. We count each of these inverse operations and sum them up to get the minimum total.
Algorithm
- Initialize
operations = 0. - Start a loop that continues as long as at least one element in
numsis non-zero. - Inside the loop, count the number of odd elements. For each odd element, decrement it by 1 and add 1 to a temporary
incrementscounter. - Add the
incrementscount to the totaloperations. - After processing all odd numbers, if the array is not yet all zeros, it means a "double" operation is required. Increment
operationsby 1. - Divide every element in the array by 2.
- Once the loop terminates (all elements are zero), return the total
operations.
Walkthrough
The algorithm iteratively transforms the nums array to an all-zero array. In each iteration of a main loop, it first handles all odd numbers. It scans the array, and for every odd number it finds, it decrements the number by one and counts this as one operation. After this pass, all numbers in the array are even. If the array is not yet all zeros, we can perform a "halve" operation on all elements. This counts as one more operation. This entire process is repeated until all elements in the array become zero. The total count of operations gives the minimum number required.
public int minOperations(int[] nums) { int operations = 0; int n = nums.length; while (true) { int zeros = 0; int increments = 0; for (int i = 0; i < n; i++) { if (nums[i] % 2 == 1) { nums[i]--; increments++; } if (nums[i] == 0) { zeros++; } } operations += increments; if (zeros == n) { break; } // This accounts for the single "double all" operation operations++; for (int i = 0; i < n; i++) { nums[i] /= 2; } } return operations;}Complexity
Time
O(N * log(M)), where N is the number of elements in `nums` and M is the maximum value in `nums`. The main `while` loop runs approximately `log(M)` times, as the maximum element is halved in each iteration. Inside the loop, we perform O(N) work by iterating through the array.
Space
O(1) because the input array is modified in-place and only a few extra variables are used.
Trade-offs
Pros
It's a very intuitive way to conceptualize the problem by reversing the process.
Correctly finds the minimum number of operations.
Cons
Modifies the input array, which might be an undesirable side effect.
Less efficient in practice than the per-number analysis due to multiple passes over the entire array. In each step of the reduction (halving), it needs to scan the array at least once to find odd numbers and another time to halve them.
This optimized approach analyzes the contribution of each number to the total operations without simulating the step-by-step transformation. It decouples the two types of operations:
-
Increment Operations: An increment is used to turn an even number into an odd one. In binary, this corresponds to flipping a 0 to a 1. The total number of increments is the sum of increments needed for each number, which equals the total number of set bits (1s) across all numbers in their binary representations.
-
Double Operations: A double operation is a left bit shift applied to all numbers simultaneously. The total number of doublings is therefore limited by the number that requires the most doublings to be formed. This is equivalent to the highest power of 2 needed, which corresponds to the position of the most significant bit in the largest number.
Algorithm
- The number of increment operations needed to form a number
xis equal to the number of set bits (1s) in its binary representation. - The number of double operations is applied to the whole array and is thus determined by the element that needs the most doublings. The number of doublings for a number
xisfloor(log2(x)). - Initialize
totalIncrements = 0andmaxDoubles = 0. - Iterate through each
numin thenumsarray. - For each
num, add its bit count (Integer.bitCount(num)) tototalIncrements. - Calculate the number of doublings it needs, which is
floor(log2(num)). This can be found by calculating(number of bits in integer type - 1) - number of leading zeros. - Update
maxDoubleswith the maximum number of doublings seen so far. - The final result is
totalIncrements + maxDoubles.
Walkthrough
By observing the effect of the operations on the binary representation of numbers, we can derive a direct formula. Each 'increment' operation corresponds to setting a bit to 1. Each 'double' operation corresponds to a left shift for all numbers. Therefore, the total number of increments is the sum of all set bits in the target numbers. The number of 'double' operations is determined by the number that needs the most left shifts, which is the one with the most significant bit at the highest position. We can iterate through the nums array once, accumulating the counts for increments (sum of set bits) and tracking the maximum number of doublings required (max(floor(log2(num)))).
Java provides efficient built-in functions like Integer.bitCount() to count set bits and Integer.numberOfLeadingZeros() to help calculate the base-2 logarithm, leading to a very efficient implementation.
public int minOperations(int[] nums) { int totalIncrements = 0; int maxDoubles = 0; for (int num : nums) { if (num == 0) { continue; } // Each set bit requires one increment operation. totalIncrements += Integer.bitCount(num); // The number of doublings is determined by the most significant bit's position. // floor(log2(num)) can be calculated this way for positive integers. int doubles = (Integer.SIZE - 1) - Integer.numberOfLeadingZeros(num); maxDoubles = Math.max(maxDoubles, doubles); } return totalIncrements + maxDoubles;}Complexity
Time
O(N), where N is the number of elements in `nums`. We iterate through the array once. The operations inside the loop (`bitCount`, `numberOfLeadingZeros`) take constant time as integers have a fixed number of bits (32).
Space
O(1), as it only requires a few variables to store the running counts.
Trade-offs
Pros
Highly efficient, with a time complexity linear in the size of the input array.
Does not modify the input array.
The logic is very clean and performs the calculation in a single pass.
Cons
The direct mapping of operations to bit manipulation concepts (popcount and log2) might be less immediately obvious than the simulation approach.
Solutions
Solution
class Solution {public int minOperations(int[] nums) { int ans = 0; int mx = 0; for (int v : nums) { mx = Math.max(mx, v); ans += Integer.bitCount(v); } ans += Integer.toBinaryString(mx).length() - 1; return ans; }}class Solution {public: int minOperations(vector<int> &nums) { int ans = 0; int mx = 0; for (int v : nums) { mx = max(mx, v); ans += __builtin_popcount(v); } if (mx) ans += 31 - __builtin_clz(mx); return ans; }};class Solution: def minOperations(self, nums: List[int]) -> int: return sum( v . bit_count() for v in nums) + max(0, max(nums). bit_length() - 1)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.