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