मान लीजिए हमारे पास एक धनात्मक पूर्णांक n है और हम निम्नलिखित ऑपरेशन कर सकते हैं:
- यदि
nसम है, तोnकोn/2से बदलें। - यदि
nविषम है, तो आपnको या तोn + 1याn - 1से बदल सकते हैं।
हमें n को 1 बनाने के लिए आवश्यक न्यूनतम प्रतिस्थापन की संख्या ढूंढनी है?
उदाहरण के लिए, यदि संख्या 7 है, तो उत्तर 4 होगा, जैसे 7 → 8 → 4 → 2 → 1 या 7 → 6 → 3 → 2 → 1।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
ret := 0,n := x- जब तक
- यदि
nसम है, तोn := n / 2 - अन्यथा जब
nविषम है- यदि
n = 3याn/2सम है, तोnको 1 से घटाएं, अन्यथाnको 1 से बढ़ाएं
- यदि
retको 1 से बढ़ाएं
- यदि
retलौटाएं।
उदाहरण (C++)
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; typedef long long int lli; class Solution { public: int bitCount(int x){ int ret = 0; while(x){ ret++; x >>= 1; } return ret; } int integerReplacement(int x) { int ret = 0; lli n = x; while(n > 1){ if(n % 2 == 0){ n >>= 1; } else if(n & 1){ if(n == 3 || (((n >> 1) & 1 )== 0)){ n--; } else { n++; } } ret++; } return ret; } }; main(){ Solution ob; cout << (ob.integerReplacement(7)); }इनपुट
7
आउटपुट
4