অনন্ত নাম্বার লাইনে লক্ষ্যে যেতে ন্যূনতম মুভের সংখ্যা বের করা C++-তে

মনে করুন আমাদের অনন্ত নাম্বার লাইনে (-inf থেকে +inf) একটি টার্গেট পজিশন আছে। ০ থেকে শুরু করে, আমাদের লক্ষ্যে যেতে হবে বর্ণিত পদ্ধতিতে। i-তম মুভে, আমরা i স্টেপ যেতে পারি বাম বা ডান। আমাদের ন্যূনতম কতগুলো মুভ লাগবে সেটি বের করতে হবে। মনে করুন টার্গেট হল ২, তাহলে ন্যূনতম স্টেপ হবে ৩। ০ থেকে ১, ১ থেকে -১ এবং -১ থেকে ২।

এই সমস্যাটি সমাধানের জন্য, কিছু গুরুত্বপূর্ণ পয়েন্ট মনে রাখতে হবে। যদি টার্গেট নেতিবাচক হয়, তবে সেটি ধনাত্মক হিসেবে নিন, কারণ নাম্বার লাইন দুটি পাশে একই। সমাধানের জন্য আইডিয়া হল একদিকেই যেতে পারার পর্যন্ত যান। তাই ০ থেকে ১, ১ থেকে ৩ (1+2), ৩ থেকে ৬ (1+2+3) এবং এভাবেই চলুন। এইভাবে যদি n-তম মুভের পর টার্গেট পাওয়া যায়, তবে সহজেই মুভের সংখ্যা রিটার্ন করুন। কিন্তু যদি পাওয়া পয়েন্ট টার্গেটের চেয়ে বড় হয়, তবে পার্থক্য বের করুন কতটুকু বেশি হয়েছে। এখন দেখা যাক, যদি i-তম স্টেপ পিছনে যাই, তবে যোগফল হবে (sum - 2i)। এখন যদি sum-2i টার্গেট হয়, তবে ফলাফল পাওয়া গেল। কিন্তু পার্থক্য জোড় বা বিজোড় হতে পারে। জোড় হলে n রিটার্ন করুন, অন্যথায়, একটা অধিক স্টেপ নিন। তাই n+1 যোগ করুন sum-এ এবং আবার পার্থক্য নিন। যদি 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