ধরুন অসীম সংখ্যা রেখায় আমাদের একটি সংখ্যার অবস্থান আছে। (-inf থেকে +inf)। 0 থেকে শুরু করে, বর্ণিত হিসাবে চলমান হয়ে লক্ষ্যে পৌঁছাতে হবে। এই পদক্ষেপে, আমরা বাম বা ডান ধাপে যেতে পারি। আমাদের প্রয়োজন ন্যূনতম সংখ্যক চাল খুঁজে বের করতে হবে। ধরুন লক্ষ্য 2, তাই ন্যূনতম ধাপ হবে 3টি। 0 থেকে 1, 1 থেকে -1 এবং -1 থেকে 2 পর্যন্ত।
এই সমস্যা সমাধানের জন্য, আমাদের কিছু গুরুত্বপূর্ণ বিষয় মনে রাখতে হবে। যদি লক্ষ্যটি নেতিবাচক হয়, তবে এটিকে ইতিবাচক হিসাবে নিন, কারণ সংখ্যা লাইনটি অভিন্ন। সমাধানের জন্য, ধারণাটি যতক্ষণ সম্ভব এক দিকে সরানো হয়। সুতরাং 0 থেকে 1 এ যান, 1 থেকে 3 এ যান (1 + 2), 3 থেকে 6 (1 + 2 + 3) এ যান ইত্যাদি। এইভাবে যদি nth মুভের পরে টার্গেট পাওয়া যায়, তাহলে সহজভাবে চালের সংখ্যা ফেরত দিন। কিন্তু প্রতিষ্ঠিত বিন্দু যদি লক্ষ্যের চেয়ে বড় হয়, তাহলে আমরা কতটা এগিয়ে আছি তার পার্থক্য খুঁজে বের করতে হবে। এখন আমরা দেখতে পাচ্ছি, যদি আমরা ith ধাপ পিছিয়ে যাই, তাহলে যোগফল হবে (sum – 2i)। এখন যদি sum-2i টার্গেট হয়, তাহলে আমরা ফলাফল পেয়েছি। কিন্তু পার্থক্য জোড় বা বিজোড় হতে পারে। জোড়ের জন্য, ফলাফল হিসাবে n ফেরত দিন, অন্যথায়, আমরা আরও একটি পদক্ষেপ নিই। তাই যোগফলের সাথে n + 1 যোগ করুন এবং এখন আবার পার্থক্য নিন। যদি n + 1 টার্গেট হয়, তাহলে ফিরে যান, অন্যথায় n + 2 দিয়ে আরও একটি ধাপ করুন।
উদাহরণ
#include<iostream>
#include<cmath>
using namespace std;
int minStepToTarget(int target) {
target = abs(target);
int sum = 0, min_step = 0;
while (sum < target || (sum - target) % 2 != 0) {
min_step++;
sum += min_step;
}
return min_step;
}
int main() {
int target = 11;
cout << "Minimum step to reach the target is: " << minStepToTarget(target);
} আউটপুট
Minimum step to reach the target is: 5
