मान लीजिए हमारे पास अनंत संख्या रेखा में एक संख्या की स्थिति है। (-इन्फ से +इन्फ)। 0 से शुरू करके हमें बताए अनुसार आगे बढ़ते हुए लक्ष्य तक पहुंचना है। इस चाल में, हम या तो बाएँ या दाएँ कदम जा सकते हैं। हमें आवश्यक चालों की न्यूनतम संख्या ज्ञात करनी है। मान लीजिए लक्ष्य 2 है, तो न्यूनतम चरण 3 होंगे। 0 से 1 तक, 1 से -1 तक और -1 से 2 तक।
इस समस्या को हल करने के लिए हमें कुछ महत्वपूर्ण बिंदुओं को याद रखना होगा। यदि लक्ष्य ऋणात्मक है, तो इसे केवल धनात्मक मान लें, क्योंकि संख्या रेखा समान है। हल करने के लिए, विचार को यथासंभव लंबे समय तक एक दिशा में ले जाना है। तो 0 से 1 तक, 1 से 3 (1 + 2), 3 से 6 (1 + 2 + 3) और इसी तरह। इस प्रकार यदि nवीं चाल के बाद लक्ष्य मिल जाता है, तो बस चालों की संख्या लौटा दें। लेकिन अगर स्थापित बिंदु लक्ष्य से बड़ा है, तो हमें कितना आगे है इसके बीच का अंतर खोजना होगा। अब हम देख सकते हैं, यदि हम एक कदम पीछे की ओर बढ़ते हैं, तो योग (योग – 2i) होगा। अब अगर योग -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