Leetcode 1558. Minimum Numbers of Function Calls to Make Target Array

Problem statement

https://leetcode.com/problems/minimum-numbers-of-function-calls-to-make-target-array/

Solution

Use greedy strategy: each time when we have odd numbers, subtract 1. Then divide everything by 2.

Complexity

It is O(n log M) for time and O(1) for space, where M = max(A).

Code

class Solution:
    def minOperations(self, A):
        ans = 0
        while True:
            ans += sum(x%2 for x in A)
            if max(A) <= 1: break
            A = [x//2 for x in A]
            ans += 1
        return ans