BinarySearch 0902 Make Target List with Increment and Double Operations

Problem statement

https://binarysearch.com/problems/Make-Target-List-with-Increment-and-Double-Operations/

Solution

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

Complexity

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

Code

class Solution:
    def solve(self, A):
        if not A: return 0
        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