[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.

It first appeared in Leetcode Biweekly Contest 33. Although dynamic programming could be applied here, it turns out that bit operations are incredibly faster(276ms vs. 1468ms). Moreover, operations like left shift, right shift, \pm 1 imply potential approaches using bits.

Dynamic programming

Assuming a number num, a and b refer to the number of operations of adding 1 and the number of operations of being divided by 2. Noticing that the operations of dividing could be shared among all numbers, the result should be the sum of a for each number plus the maximum of b among all numbers.

Therefore we can apply DFS to find the a and b for each num, and add memorization to transform it into a top-down dynamic programming approach (details about DFS to DP could be found at Depth-First-Search(DFS) vs Dynamic Programming(DP)).

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        memo = {0:(0,0)} # (operation of +1, operation of *2)
        def helper(num):
            if num not in memo:
                if num % 2 == 1:
                    a,b = helper(num-1)
                    memo[num] = (a+1,b)
                else:
                    a,b = helper(num//2)
                    memo[num] = (a,b+1)
            return memo[num]
        a = b = 0
        for num in nums:
            tmpa,tmpb = helper(num)
            a += tmpa
            b = max(b,tmpb)
        return a + b

Dynamic programming – optimized

We can optimise this DP by observing that, we would always prefer dividing than adding when it’s possible. Or to put it in another way, we can do at most 1 continuous +1 operation. This is quite similar to [Leetcode]1553. Minimum Number of Days to Eat N Oranges.

Proof by contradiction

Given number i, assuming i-1-1 is optimal.

• When the next operation is ‘/2’, we have (i-1-1)/2 which takes 3 operations. But we can achieve it by (i/2)-1 which takes only 2 operations. This could be extended to n ‘-1’ operations.
• When the operations are all ‘-1’. For number i, we can easily prove that i>i/2+1 where the former one denotes i ‘-1’ operations and the latter one denotes a ‘/2’ operation and i/2 ‘-1’ operations.

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        @lru_cache(None)
        def helper(num):
            if num < 2: return num,0
            a,b = helper(num//2)    
            return a+num%2,b+1
        a = b = 0
        for num in nums:
            tmpa,tmpb = helper(num)
            a += tmpa
            b = max(b,tmpb)
        return a + b

Bit operations

This approach is from @lee215.

Given a number num, we could observe that:

• if num%2==0, then we divide it by two, i.e., right shift by 1
• if num%2==1, then we minus 1 from it

Therefore, the number of operations of dividing should be the length of the binary representation of num while the number of operations of adding should be the number of 1 in its binary representation.

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        return sum(bin(num).count('1') for num in nums) +\
                len(bin(max(nums)))-2-1

Reference

• https://leetcode.com/problems/minimum-numbers-of-function-calls-to-make-target-array/
• https://shawnlyu.com/algorithms/depth-first-searchdfs-vs-dynamic-programmingdp/
• https://leetcode.com/problems/minimum-numbers-of-function-calls-to-make-target-array/discuss/805740/JavaC%2B%2BPython-Bit-Counts