আমাদের একটি target[] অ্যারে দেওয়া আছে। সব শূন্য অ্যারে [0,0,0...] থেকে target[]-এ পৌঁছাতে হবে শুধু দুটি অপারেশন দিয়ে: (১) ইনক্রিমেন্ট - প্রতিটি এলিমেন্ট আলাদা করে ১ বাড়ানো (n এলিমেন্টে n স্টেপ), (২) ডাবলিং - পুরো অ্যারে একসাথে দ্বিগুণ (১ স্টেপ)। ন্যূনতম স্টেপ বের করা।
ইনপুট
target[]= { 1,2,2,3 }
আউটপুট
Minimum steps to reach target from {0,0,0,0} : 6
ব্যাখ্যা: {0,0,0,0} -> ৩ ইনক্রিমেন্ট -> {0,1,1,1} -> ১ ডাবলিং -> {0,2,2,2} -> ২ ইনক্রিমেন্ট -> {1,2,2,3}। মোট ৩+১+২=৬।
ইনপুট
target[]= { 3,3,3 }
আউটপুট
Minimum steps to reach target from {0,0,0} : 7
ব্যাখ্যা: {0,0,0} -> ৩ ইনক্রিমেন্ট -> {1,1,1} -> ১ ডাবলিং -> {2,2,2} -> ৩ ইনক্রিমেন্ট -> {3,3,3}। মোট ৭।
প্রোগ্রামে ব্যবহৃত পদ্ধতি (রিভার্স অ্যাপ্রোচ)
- target[] থেকে শূন্য অ্যারেতে যাওয়া।
- সব এলিমেন্ট ইভেন করা (অড হলে ১ বিয়োগ, কাউন্ট++)।
- সব ইভেন হলে পুরো অ্যারে ২ দিয়ে ভাগ (কাউন্ট++)।
- এটি রিপিট যতক্ষণ না ম্যাক্স ভ্যালু ১ হয়।
- শেষে ১ গুলো ০ করতে কাউন্ট++।
- টোটাল কাউন্ট রিটার্ন।
উদাহরণ কোড
#include <bits/stdc++.h>
using namespace std;
int minSteps(int target[], int n){
int count = 0, max = target[0], pos = 0;
for(int i=0; i= max){ max = target[i]; pos = i; }
}
while(target[pos] != 1){
for(int i=0; i আউটপুট
Minimum steps to get the given desired array:15
