ধরুন আপনি একটি অসীম সংখ্যা রেখায় 0 অবস্থানে দাঁড়িয়ে আছেন। এখন পজিশন টার্গেটে গোল আছে। এখানে প্রতিটি পদক্ষেপে, আপনি হয় বাম দিকে বা ডান দিকে যেতে পারেন। n-ম পদক্ষেপের সময় (1 থেকে শুরু), আপনি n পদক্ষেপ নিন। আমাদের গন্তব্যে পৌঁছানোর জন্য প্রয়োজনীয় ন্যূনতম সংখ্যক ধাপ খুঁজে বের করতে হবে। সুতরাং যদি ইনপুট টার্গেট =3 এর মত হয়, তাহলে আমাদের 2 টি ধাপ দরকার। 0 থেকে 1, 1 থেকে 3 পর্যন্ত।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- টার্গেট :=|টার্গেট|, cnt :=0
- যখন লক্ষ্য> 0,
- cnt 1 কমিয়ে দিন
- লক্ষ্য :=লক্ষ্য –cnt
- যদি লক্ষ্য সমান হয়, তাহলে cnt ফেরত দিন, অন্যথায় cnt + 1 + cnt mod 2
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int reachNumber(int target) {
target = abs(target);
int cnt = 0;
while(target > 0){
target -= ++cnt;
}
return target % 2 == 0? cnt : cnt + 1 + cnt % 2;
}
};
main(){
Solution ob;
cout << (ob.reachNumber(3));
} ইনপুট
3
আউটপুট
2
