C++ এ প্রদত্ত কাঙ্খিত অ্যারে পেতে সর্বনিম্ন পদক্ষেপ গণনা করুন

আমাদের একটি অ্যারে টার্গেট দেওয়া হয়েছে [] যার মধ্যে সংখ্যা রয়েছে। আমাদের অবশ্যই ন্যূনতম পদক্ষেপগুলি খুঁজে বের করতে হবে যেখানে সমস্ত শূন্য [0,0,0,0…] সহ অ্যারেকে নিম্নলিখিত দুটি অপারেশন ব্যবহার করে লক্ষ্যে রূপান্তর করা যেতে পারে -

ইনক্রিমেন্ট অপারেশন - সমস্ত উপাদান 1 দ্বারা বৃদ্ধি করা যেতে পারে, প্রতিটি ইনক্রিমেন্ট অপারেশন পৃথকভাবে ধাপে গণনা করা যেতে পারে। ( n উপাদান ধাপে n বৃদ্ধির জন্য =n )
দ্বিগুণ অপারেশন - পুরো অ্যারে দ্বিগুণ হয়। সমস্ত উপাদানের জন্য এটি একবার গণনা করা হয়। (প্রতিটি দ্বিগুণ অপারেশন সমস্ত উপাদানের মানকে দ্বিগুণ করে, এটিকে ধাপে 1 হিসাবে গণনা করুন

লক্ষ্য হল লক্ষ্যে পৌঁছাতে ন্যূনতম সংখ্যক ধাপ বের করা। যেমন [0,0,0] ন্যূনতম 3টি ধাপে [1,1,1] হয়ে যেতে পারে (সমস্ত উপাদানের উপর বর্ধিত ক্রিয়াকলাপের মাধ্যমে) এবং আরও একটি দ্বিগুণ অপারেশনের মাধ্যমে [2,2,2] হয়ে যেতে পারে, এইবার মোট 4টি ধাপ ( 3 বৃদ্ধি, 1 দ্বিগুণ।

ইনপুট

target[]= { 1,2,2,3 }

আউটপুট

Minimum steps to reach target from {0,0,0,0} : 6

ব্যাখ্যা

প্রাথমিকভাবে আমাদের আছে { 0,0,0,0 }

3টি ইনক্রিমেন্ট অপারেশন { 0,1,1,1 } //বৃদ্ধি পৃথকভাবে ঘটে

1 দ্বিগুণ অপারেশন { 0,2,2,2 } // সমস্ত উপাদানে দ্বিগুণ ঘটে

2 ইনক্রিমেন্ট অপারেশন { 1,2,2,3 }

মোট ধাপ=3+1+2=6

ইনপুট

target[]= { 3,3,3 }

আউটপুট

Minimum steps to reach target from {0,0,0} : 7

ব্যাখ্যা

প্রাথমিকভাবে আমাদের আছে { 0,0,0 }

3টি ইনক্রিমেন্ট অপারেশন { 1,1,1 } //বৃদ্ধি পৃথকভাবে ঘটে

1 দ্বিগুণ অপারেশন { 2,2,2 } // সমস্ত উপাদানে দ্বিগুণ ঘটে

3 ইনক্রিমেন্ট অপারেশন { 3,3,3 }

মোট ধাপ=3+1+3=7

নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি

পূর্ণসংখ্যা অ্যারে লক্ষ্য [] পৌঁছানোর লক্ষ্য উপাদান সংরক্ষণ করে।
ফাংশন minSteps(int target[],int n) টার্গেট অ্যারে এবং এর দৈর্ঘ্য 'n' ইনপুট হিসাবে নেয় এবং সমস্ত শূন্য থেকে লক্ষ্যে পৌঁছানোর জন্য সর্বনিম্ন পদক্ষেপের গণনা ফেরত দেয়।
ভেরিয়েবল কাউন্ট স্টেপ কাউন্ট সংরক্ষণ করতে ব্যবহৃত হয়, প্রাথমিকভাবে 0।
ভেরিয়েবল ম্যাক্স ব্যবহার করা হয় সর্বোচ্চ উপাদান সংরক্ষণ করতে, প্রাথমিকভাবে লক্ষ্য[0]।
পরিবর্তনশীল pos ব্যবহার করা হয় সর্বাধিক পাওয়া সূচক, প্রাথমিকভাবে 0.
সংরক্ষণ করতে
যদি টার্গেট[] অ্যারেতে সব শূন্য থাকে তাহলে 0 রিটার্ন করুন যেহেতু কোনো পদক্ষেপের প্রয়োজন নেই। (এর জন্য (i=0;i
এখন এই পদ্ধতিতে আমরা লক্ষ্য[] থেকে সমস্ত শূন্যে পৌঁছাব।
বিজোড়গুলি থেকে 1 বিয়োগ করে সমস্ত উপাদানকে জোড় করুন। প্রতিটি বিয়োগের জন্য বৃদ্ধির গণনা (বৃদ্ধি ক্রিয়াকলাপের মতোই)
এখন আমাদের কাছে সব জোড় সংখ্যা আছে।
একই লুপে সর্বোচ্চ মান এবং এর অবস্থান খুঁজে বের করুন এবং সর্বোচ্চ এবং অবস্থান শুরু করুন।
এখন আমরা পুরো অ্যারেটিকে 2 দ্বারা ভাগ করা শুরু করি যতক্ষণ না সর্বোচ্চ মান 1 না হয়ে যায়। যদি কোনো সংখ্যা বিজোড় হয়ে যায়, তাহলে 1 হ্রাস করুন এবং গণনা বাড়ান, পুরো বিভাজন অপারেশনের জন্য একবার বৃদ্ধির গণনা করুন।
শেষে সমস্ত উপাদান 0 বা 1 হবে, সমস্ত 1 এর জন্য তাদের 0 করে এবং আবার গণনা বৃদ্ধি করে৷
গণনায় উপস্থিত পদক্ষেপ হিসাবে ফলাফল ফেরত দিন।

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
int minSteps(int target[],int n){
   int i;
   int count=0;
   int max=target[0];
   int pos=0;
   for(i=0;i<n;i++)
      if(target[i]==0)
         count++;
      //if all are zeros, same as target
      if(count==n)
         return 0;
         count=0;
         //make all even by sbtracting 1
      for(i=0;i<n;i++){
         if(target[i]%2==1){
            target[i]=target[i]-1;
            count++;
      }
      //find max value and its position
      if(target[i]>=max){
         max=target[i];
         pos=i;
      }
   }
   //diving by 2 till all elements are 1 and increase count once
   while(target[pos]!=1){
      for(i=0;i<n;i++){
         if(target[i]%2==1){
             target[i]=target[i]-1;
            count++;
      }
      target[i]=target[i]/2;
   }
   count++;
}
//whole array is {1} make zeroes and increase count
while(target[pos]!=0){
   for(i=0;i<n;i++){
      if(target[i]!=0){
         target[i]=target[i]-1;
         count++;}
      }
   }
   return count;
}
int main(){
   int target[]={15,15,15};
   cout<<"\nMinimum steps to get the given desired array:"<<minSteps(target,3);
   return 0;
}

আউটপুট

Minimum steps to get the given desired array:15