C++ में शून्य से X तक पहुंचने के लिए आवश्यक न्यूनतम जंप की संख्या

मान लीजिए हमारे पास एक पूर्णांक X है। हमें 0 से X तक पहुंचने के लिए आवश्यक न्यूनतम जंप की संख्या ढूंढनी है। पहला जंप 1 यूनिट का हो सकता है और प्रत्येक अगला जंप पिछले जंप से ठीक 1 यूनिट लंबा होगा। प्रत्येक जंप में बाएं या दाएं जा सकते हैं। उदाहरण: X=8 के लिए आउटपुट 4 है (0 → -1 → 1 → 4 → 8)।

अवलोकन

• यदि हमेशा दाएं जंप करें, तो n जंप के बाद स्थिति p = 1 + 2 + 3 + ... + n = n(n+1)/2 होगी।
• यदि k-वें जंप में बाएं जाएं, तो स्थिति p - 2k होगी।
• सावधानीपूर्वक चुनकर, n जंप के बाद आप -n(n+1)/2 और n(n+1)/2 के बीच किसी भी स्थिति पर पहुंच सकते हैं जिसकी पैरिटी n(n+1)/2 के समान हो।

C++ उदाहरण

#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 || (sumOneToN(ans) - n) & 1)
        ans++;
    return ans;
}

int main() {
    int n = 9;
    cout << "Number of jumps: " << jumps(n);
    return 0;
}

आउटपुट

Number of jumps: 5