इस समस्या में, हमें सकारात्मक दिशा या नकारात्मक दिशा को इस तरह से स्थानांतरित करने का एक वैध तरीका खोजना होगा कि हम उपयोगकर्ता द्वारा प्रदान की गई एक निश्चित सीमा के भीतर रहें।
यहां, हमें एक निश्चित अधिकतम सीमा 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-ए[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