Chương trình tìm số lần gọi hàm tối thiểu để tạo mảng mục tiêu bằng Python

Cho hàm modify(arr, op, index): op=0 tăng arr[index] lên 1; op=1 nhân đôi tất cả phần tử. Tìm số lời gọi hàm ít nhất để biến mảng 0 thành nums.

Ví dụ: nums=[1,5,3] → 7 bước.

Thuật toán

• ans = [0, 0] (ans[0]: số lần +1, ans[1]: max số lần nhân 2)
• Với mỗi n trong nums:
  • double = 0
  • While n > 0:
    • Nếu n chẵn: n //= 2; double += 1
    • Nếu n lẻ: n -= 1; ans[0] += 1
  • ans[1] = max(ans[1], double)
• Return sum(ans)

Code Python

def solve(nums):
    ans = [0, 0]
    for n in nums:
        double = 0
        while n:
            if n % 2 == 0:
                n //= 2
                double += 1
            else:
                n -= 1
                ans[0] += 1
            ans[1] = max(ans[1], double)
    return sum(ans)

nums = [1,5,3]
print(solve(nums))

Input

[1,5,3]

Output

7