পাইথন ব্যবহার করে টার্গেট অ্যারে তৈরি করতে ন্যূনতম সংখ্যক ফাংশন কল খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের নিম্নলিখিত ফাংশনের সংজ্ঞা আছে:

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

একই আকারের একটি শূন্য অ্যারে থেকে একটি প্রদত্ত অ্যারে সংখ্যা তৈরি করার জন্য আমাদের প্রয়োজনীয় ন্যূনতম সংখ্যক ফাংশন কল খুঁজে বের করতে হবে?

সুতরাং, যদি ইনপুটটি সংখ্যার মত হয় =[1,5,3], তাহলে আউটপুট হবে 7 কারণ, প্রাথমিকভাবে সমস্ত উপাদান 0, [0,0,0]

প্রথম ধাপে দ্বিতীয় উপাদান 1 দ্বারা বৃদ্ধি করুন, তাই অ্যারে হল [0,1,0]
এটি তৈরি করতে দ্বিগুণ দ্বিতীয় উপাদান [0,2,0]
তৃতীয় উপাদানকে 1 দ্বারা বাড়ান, তাই অ্যারে হল [0,2,1]
সূচক 1 থেকে 2 পর্যন্ত দ্বিগুণ উপাদান, তাই অ্যারে হল [0,4,2]
সমস্ত উপাদান 1 দ্বারা বৃদ্ধি করুন [এখানে মোট তিনটি অপারেশন]

তাই মোট 3+4 =7 অপারেশন প্রয়োজন।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

উত্তর :=দুটি উপাদান সহ একটি অ্যারে সবই 0
প্রতিটি n সংখ্যার জন্য, করুন
- দ্বিগুণ :=0
- যখন n অ-শূন্য, কর
  - যদি n বিজোড় হয়, তাহলে
    - n :=n/2 এর ভাগফল
    - ডবল :=ডবল + 1
  - অন্যথায়,
    - n :=n - 1
    - ans[0] :=ans[0] + 1
- ans[1] :=সর্বাধিক উত্তর[1] এবং দ্বিগুণ
উত্তরের সমস্ত উপাদানের যোগফল

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

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]