[LeetCode 1558] Minimum Numbers of Function Calls to Make Target Array

Your task is to form an integer array nums from an initial array of zeros arr that is the same size as nums.

Return the minimum number of function calls to make nums from arr.

The answer is guaranteed to fit 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).

Example 4:

Input: nums = [3,2,2,4]
Output: 7

Example 5:

Input: nums = [2,4,8,16]
Output: 8

Constraints:

1 <= nums.length <= 10^5
0 <= nums[i] <= 10^9

For each operation, we can do one of the following:

(1) pick an i and increment A[i] by 1;

(2) multiply all the numbers in A by 2.

Incorrect attempt during contest

Key observations:

1. Obviously option 2 is always at least as good as option 1 toward reaching the final target array. So we should use the multipy option as many times as we can until we reach a state that further applying multiplication option would cause some numbers go over the intended target values.

2. To reach the final target, each position's number will have at least one option 1 operation: either to change 0 to 1 at the beginning or later time, or keep adding 1 to reach the final value after we can not use multiplication anymore.

3. The number of multiplications applied is determined by the max number in the target array. Why? Because for smaller target values, we can always keep them as 0s and only add 1 to the bigger target values then apply some * 2 operations, then add 1 to these smaller values and apply some more * 2 operations. The key here is 0 * 2 is still 0. In another word, all * 2 operations are shared among all numbers and we can freely choose the number of * 2 that makes a change. For smaller numbers we want to leave them as 0 for a while before making them 1 then start to multiply by 2.

Incorrect algorithm: First we find the max value and use it to calculate how many * 2 we can have starting from value 1. Then iterate the target array and for each target value V, do this: starting from 1, keep * 2 until doing it one more time will cause the new value exceeds V, call this new value T. Then we'll need another V - T +1 operations. Before moving to the next value, add 1 to the final count as we must go from 0 to 1 first.

Consider this counter example: [1000], the correct answer should be 15, but my solution outputs 498! So what goes wrong here? Well, the way I tried to construct V is to start from 1, then keep multiplying by 2 until I can not anymore. Only by then I would consider the +1 operations, which is the difference between V and T. 512 * 2 > 1000, so I stopped at 512 by using one +1 and 9 mulitiplications. 1000 - 512 + 10 = 498. The right action should be as follows, using only 15 operations:

0 + 1 = 1

1 * 2 = 2

2 + 1 = 3

3 * 2 = 6

6 + 1 = 7

7 * 2 = 14

14 + 1 = 15

15 * 2 = 30

30 + 1 = 31

31 * 2 = 62

62 * 2 = 124

124 + 1 = 125

125 * 2 = 250

250 * 2 = 500

500 * 2 = 1000

So the problem is that we do not have to only use back to back * 2 and back to back +1, we can mix them together to reach a target value faster. As a result, instead of going forward from 0 to V, we should go backward from V to 0 as described in the correct algorithm below.

class Solution {
    public int minOperations(int[] nums) {
        int maxV = 0;
        for(int v : nums) {
            maxV = Math.max(maxV, v);
        }
        int mul = 0;
        int p = 1;
        while(p < maxV) {
            p = p * 2;
            mul++;
        }
        if(p > maxV) {
            mul--;
            p = p / 2;
        }
        
        int ans = mul;        
        for(int v : nums) {
            int t = 1;
            while(t < v) {
                t = t * 2;
            }
            if(t > v) {
                t = t / 2;
            }
            //0 -> 1
            ans++;
            ans += (v - t);
        }
        return ans;
    }
}

Correct Algorithm

Based on the above analysis, it is clear that the right algorithm is to check each target value backward, from V to 0. As long as V is > 0, we need some more operations: if V is odd, we must came from a smaller even value by adding 1 to it, so we use one +1 and V--; if V is even, it means we came from V / 2, so we use one * 2 and V = V / 2. When iterating each target value, we also keep track of the maximum multiplications needed, this is the total * 2 we need for getting to the entire target array.

class Solution {
    public int minOperations(int[] nums) {
        int inc = 0, mul = 0;
        for(int v : nums) {
            int currMul = 0;
            while(v > 0) {
                if(v % 2 != 0) {
                    inc++;
                    v--;
                }
                else {
                    v /= 2;
                    currMul++;
                }
            }
            mul = Math.max(mul, currMul);
        }
        return inc + mul;
    }
}