এই সমস্যায়, আমাদের ইতিবাচক দিক বা নেতিবাচক দিক থেকে সরানোর জন্য একটি বৈধ উপায় খুঁজে বের করতে হবে যাতে আমরা ব্যবহারকারীর দ্বারা প্রদত্ত একটি নির্দিষ্ট সীমার মধ্যে থাকি৷
এখানে, আমাদেরকে একটি নির্দিষ্ট সর্বোচ্চ সীমা K দেওয়া হয়েছে, যেটি সর্বাধিক মান যেখানে আমরা সরতে পারি এবং সরানোর জন্য n ধনাত্মক মানগুলির একটি অ্যারে। আমাদের সরানোর জন্য ক্রমটি যেমন ইতিবাচক বা নেতিবাচক দিকগুলি ফিরিয়ে দিতে হবে যাতে এটি কখনই K মান অতিক্রম না করে।
বিষয়টি আরও ভালোভাবে বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
Input : K = 56 and the array is [25 , 14 , 31 , 16 , 5]. Output : positive positive negative positive positive.
ব্যাখ্যা
প্রথমে আমরা পরীক্ষা করব 0 + a[0] =0+25 =25 <56 হ্যাঁ, তারপরে আমরা ইতিবাচক দিকে অগ্রসর হব।
এখন, আমরা পরীক্ষা করব যে 25 + a[1] =25+14 =39 <56 হ্যাঁ, তাহলে আমরা ইতিবাচক দিকে অগ্রসর হব।
এখন, আমরা 29 + a[2] =39+31 =70 <56 না হলে পরীক্ষা করব, তারপরে আমরা 39 - a[2] =39 - 31 =8> 0 কিনা তা পরীক্ষা করব, তারপর আমরা একটি নেতিবাচক দিকে চলে যাব .
আমরা পরীক্ষা করব 8 + a[3] =8+16 =24 <56 হ্যাঁ, তাহলে আমরা ইতিবাচক দিকে অগ্রসর হব।
আমরা পরীক্ষা করব 16 + a[4] =16 + 5 =21 <56 হ্যাঁ, তাহলে আমরা ইতিবাচক দিকে অগ্রসর হব।
সুতরাং, এখন এই সমস্যা সমাধানের যুক্তি তৈরি করা যাক। ইতিবাচক দিকে অগ্রসর হওয়া সীমায় পৌঁছাবে কি না তা আমাদের পরীক্ষা করতে হবে। যদি না হয়, তাহলে একটি ইতিবাচক দিকে যান। অন্যথায়, একটি নেতিবাচক দিকে সরানো নিম্ন সীমা অর্থাৎ 0 তে পৌঁছাবে কিনা তা পরীক্ষা করুন। যদি না হয়, তাহলে একটি নেতিবাচক দিকে যান। যদি উভয়ই হ্যাঁ হয় তবে ফেরত দেওয়া সম্ভব নয়৷
এই যুক্তির উপর ভিত্তি করে আমাদের কোড তৈরি করার জন্য যে অ্যালগরিদমটি অনুসরণ করতে হবে তা হল −
অ্যালগরিদম
Initially set position to 0. Step 1 : for i -> 0 to n , n is the length of array. Follow step 2 - 4. Step 2 : if initial_postition + a[i] < K, initial_position + = a[i]. Print “POSITIVE”. Step 3 : else if initial_postition - a[i] > 0, initial_position - = a[i]. Print “NEGATIVE”. Step 4 : else , print “NO MORE VALID MOVES”.
উদাহরণ
এখন, সমস্যা সমাধানের জন্য অ্যালগরিদমের বাস্তবায়ন দেখানোর জন্য একটি প্রোগ্রাম তৈরি করা যাক,
#include <iostream>
using namespace std;
void StepsTaken(int a[], int n, int k){
string res = "";
int position = 0;
int steps = 1;
for (int i = 0; i < n; i++) {
if (position + a[i] <= k && position + a[i] >= (-k)) {
position += a[i];
cout<<"POSITIVE \t";
}
else if (position - a[i] >= -k && position - a[i] <= k) {
position -= a[i];
cout<<"NEGATIVE \t";
} else {
cout << -1;
return;
}
}
cout << res;
}
int main(){
int a[] = { 12 , 24 , 9 , 17 , 8};
int n = sizeof(a) / sizeof(a[0]);
int k = 40;
StepsTaken(a, n, k);
return 0;
} আউটপুট
POSITIVE POSITIVE NEGATIVE NEGATIVE POSITIVE
