Minimum Numbers of Function Calls to Make Target Array - Solution & Explanation
Problem Statement
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
Approach Overview
Problem Overview: You start with an array of zeros and want to build the target array using two operations: increment a single element by 1, or double every element in the array. The task is to compute the minimum number of function calls needed to transform the zero array into the target array.
Approach 1: Greedy Reverse Simulation (O(n log M) time, O(1) space)
Instead of building the array from zeros, think in reverse. Start from the target array and reduce it to all zeros. If an element is odd, the last operation must have been an increment, so subtract 1 from that element. If all elements are even, the last operation must have been a global doubling, so divide every element by 2. This greedy logic works because doubling affects all elements simultaneously while increments affect only one index. Repeating this process until all elements reach zero gives the minimum number of operations.
Approach 2: Bitwise Analysis (O(n log M) time, O(1) space)
The operations map directly to binary representation. Every 1 bit in a number corresponds to an increment operation. Every bit shift to the left corresponds to a doubling operation applied to the entire array. For each element, count the number of set bits using bit manipulation; this gives the total number of increment operations. Then track the maximum bit length among all numbers, which determines how many doubling operations are required. The final answer is the sum of all set bits plus (max_bit_length - 1) doubling operations.
This works because doubling the array is equivalent to a left shift in binary. Increment operations fill in the 1 bits, while doubling operations move values into higher bit positions. Iterating through the array once and analyzing the bits of each number yields the optimal result.
Both approaches rely on understanding how binary representation reflects the allowed operations. The bitwise method is typically simpler and avoids modifying the array, making it the most common interview solution.
Recommended for interviews: Use the Bitwise Analysis approach. Interviewers expect you to recognize that increment operations correspond to set bits and doubling corresponds to binary shifts. The greedy reverse idea shows strong intuition, but the bit manipulation solution demonstrates deeper understanding of binary operations and runs in linear time relative to the array size. Related concepts appear frequently in problems involving array processing, greedy algorithms, and bit manipulation.
Approach 1: Bitwise Analysis
This approach considers the bitwise representation of each number in the array. The idea is to count the number of doubling operations as the highest bit set in any of the numbers. Count the increment operations as the number of 1s in their binary representation. This exploits the fact that doubling corresponds to left bit shifting, and an increment corresponds to toggling a 0 to 1.
The C code iterates over each number, converting it to binary bit by bit. Odd values increment the counter while each full divide by 2 counts toward the maximum number of doubles required. This leverages an understanding of binary representation, counting total required operations efficiently.
Complexity
Time Complexity: O(n * log(max(nums)))
Space Complexity: O(1)
Approach 2: Greedy Approach
A greedy approach would determine the desired number by working backward from nums to the filled with zeros array. By halving even numbers and simply subtracting one from odd numbers, you can efficiently track the number of operations required. This way, the need to simulate the process is avoided by handling actual numerical reduction.
This C solution runs similarly to bitwise analysis, yet focuses on decrementing to determine processing steps. Essentially, it mirrors building the target array by thinking through each respective num's reduction instead.
Complexity
Time Complexity: O(n * log(max(nums)))
Space Complexity: O(1)
Approach 3: Default Approach
Try this approach in the editor βComplexity Comparison
| Approach | Complexity |
|---|---|
| Bitwise Analysis | Time Complexity: O(n * log(max(nums))) |
| Greedy Approach | Time Complexity: O(n * log(max(nums))) |
| Default Approach | β |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Reverse Simulation | O(n log M) | O(1) | When reasoning about operations step-by-step or explaining the logic intuitively in interviews |
| Bitwise Analysis | O(n log M) | O(1) | Best general solution; counts set bits and maximum bit length efficiently without modifying the array |
Video Solution
θ±θ±ι ± LeetCode 1558. Minimum Numbers of Function Calls to Make Target Array - ε·ι’ζΎε·₯δ½ EP351 β’ Hua Hua β’ 1,308 views views
Watch 9 more video solutions βFrequently Asked Questions
Is Minimum Numbers of Function Calls to Make Target Array easy or hard?
Minimum Numbers of Function Calls to Make Target Array Python/Java solution
How to solve Minimum Numbers of Function Calls to Make Target Array in O(n)?
What is the best approach for Minimum Numbers of Function Calls to Make Target Array?
Is Minimum Numbers of Function Calls to Make Target Array asked at Google/Amazon/Meta?
What data structure is used in Minimum Numbers of Function Calls to Make Target Array?
What is the time complexity of Minimum Numbers of Function Calls to Make Target Array?
Ready to solve this problem?
Practice Minimum Numbers of Function Calls to Make Target Array with our built-in code editor and test cases.
Practice on FleetCode