Skip to content

1558. Minimum Numbers of Function Calls to Make Target Array

Description

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

Solutions

Solution 1

Thinking

Start from zeros; an operation either increments one entry or doubles the whole array. \(n\le 10^5\) and \(nums[i]\le 10^9\), so we cannot simulate values. Doubling is a simultaneous left shift; an increment writes one \(1\)-bit of some number.

Each \(v\) needs \(v.\mathrm{bit\_count}()\) increments, and the shared doublings equal the bit length of the maximum minus one. Their sum is the minimum number of calls.

1
2
3
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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
func minOperations(nums []int) int {
    ans, mx := 0, 0
    for _, v := range nums {
        mx = max(mx, v)
        for v > 0 {
            ans += v & 1
            v >>= 1
        }
    }
    if mx > 0 {
        for mx > 0 {
            ans++
            mx >>= 1
        }
        ans--
    }
    return ans
}

Comments