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