Your task is to form an integer arraynums
from an initial array of zerosarr
that is the same size asnums
. Return the minimum number of function calls to makenums
fromarr
. 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 takes3
operations. But we can achieve it by(i/2)-1
which takes only2
operations. This could be extended ton
‘-1’ operations. - When the operations are all ‘-1’. For number
i
, we can easily prove thati>i/2+1
where the former one denotesi
‘-1’ operations and the latter one denotes a ‘/2’ operation andi/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