Python을 사용하여 대상 배열을 만들기 위한 최소 함수 호출 수를 찾는 프로그램

<시간/>

다음과 같은 함수 정의가 있다고 가정합니다.

def modify(arr, op, index):
   if op == 0:
      arr[index] += 1
   if op == 1:
      for i in range(len(arr)):
         arr[i] *=2

동일한 크기의 하나의 0 배열에서 주어진 배열 숫자를 만드는 데 필요한 최소 함수 호출 수를 찾아야 합니까?

따라서 입력이 nums =[1,5,3]과 같으면 출력은 처음에 모든 요소가 0, [0,0,0]

이기 때문에 7이 됩니다.

첫 번째 단계에서 두 번째 요소를 1만큼 증가시키므로 배열은 [0,1,0]
입니다.
[0,2,0]
으로 만들기 위해 두 번째 요소를 두 배로 늘립니다.
세 번째 요소를 1만큼 증가시켜 배열이 [0,2,1]
이 되도록 합니다.
인덱스 1에서 2까지 요소를 이중화하므로 배열은 [0,4,2]
입니다.
모든 요소를 1 증가 [여기서 총 3가지 작업]

총 3+4 =7개의 작업이 필요합니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

ans :=요소가 두 개인 배열은 모두 0입니다.
숫자의 각 n에 대해 수행
- 더블 :=0
- n이 0이 아닌 동안 수행
  - n이 홀수이면
    - n :=n/2의 몫
    - 더블 :=더블 + 1
  - 그렇지 않으면
    - n :=n - 1
    - ans[0] :=ans[0] + 1
- ans[1] :=최대 ans[1] 및 이중
ans
의 모든 요소의 합계를 반환합니다.

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

def solve(nums):
   ans = [0, 0]
   for n in nums:
      double = 0
      while(n):
         if not n%2:
            n = 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))

입력

[1,5,3]