मान लीजिए कि हमारे पास एक पूर्णांक X है। हमें 0 से X तक पहुँचने के लिए आवश्यक न्यूनतम छलांगों की संख्या ज्ञात करनी है। पहली छलांग एक इकाई की लंबाई की हो सकती है और प्रत्येक क्रमिक छलांग लंबाई में पिछली छलांग की तुलना में ठीक एक इकाई लंबी होगी। इसे प्रत्येक छलांग में बाएं या दाएं जाने की अनुमति है। तो यदि X =8 है, तो आउटपुट 4 है। 0 → -1 → 1→ 4 → 8 संभावित चरण हैं।
अगर हम ध्यान से देखें तो हम कह सकते हैं कि
- यदि आपने हमेशा सही दिशा में छलांग लगाई है, तो n छलांग लगाने के बाद आप बिंदु p =1 + 2 + 3 +… + n पर होंगे
- अगर हम बाईं ओर भी कूद सकते हैं, तो kth जंप पर आप बिंदु p – 2k पर होंगे।
- यदि हम सावधानी से चुनते हैं कि कौन सी छलांग बाईं ओर जाती है और कौन सी दाईं ओर जाती है, तो n छलांग के बाद, आप n(n+1)/2 और –(n*(n+1) / 2 के बीच के बिंदु पर हो सकते हैं ), n(n+1)/2 के समान समता के साथ।
उदाहरण
#include<iostream>
#include<cmath>
using namespace std;
inline int sumOneToN(int n) {
return (n * (n + 1)) / 2;
}
int jumps(int n) {
n = abs(n);
int ans = 0;
while (sumOneToN(ans) < n or (sumOneToN(ans) - n) & 1)
ans++;
return ans;
}
int main() {
int n = 9;
cout << "Number of jumps: " << jumps(n);
} आउटपुट
Number of jumps: 5