# Minimum Numbers of Function Calls to Make Target Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-numbers-of-function-calls-to-make-target-array)
Canonical: https://scaleengineer.com/dsa/problems/minimum-numbers-of-function-calls-to-make-target-array
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array
---
## Problem
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:

![](https://assets.glich.co/dsa/minimum-numbers-of-function-calls-to-make-target-array/image0.png) 

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 <= 105`
* `0 <= nums[i] <= 109`

# Approaches
## Iterative Reverse Simulation
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.
**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.
**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.
### Explanation
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.

```java
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;
}
```
### Algorithm
- Initialize `operations = 0`.
- Start a loop that continues as long as at least one element in `nums` is 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 `increments` counter.
- Add the `increments` count to the total `operations`.
- After processing all odd numbers, if the array is not yet all zeros, it means a "double" operation is required. Increment `operations` by 1.
- Divide every element in the array by 2.
- Once the loop terminates (all elements are zero), return the total `operations`.

## Optimized Per-Number Analysis using Bit Manipulation
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:

1.  **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.

2.  **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.
**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.
**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.
### Explanation
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.

```java
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;
}
```
### Algorithm
- The number of increment operations needed to form a number `x` is 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 `x` is `floor(log2(x))`.
- Initialize `totalIncrements = 0` and `maxDoubles = 0`.
- Iterate through each `num` in the `nums` array.
- For each `num`, add its bit count (`Integer.bitCount(num)`) to `totalIncrements`.
- 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 `maxDoubles` with the maximum number of doublings seen so far.
- The final result is `totalIncrements + maxDoubles`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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)

```