मान लीजिए कि हमारे पास एक सकारात्मक पूर्णांक 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
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
रिट:=0, एन:=एक्स
-
जबकि n> 1
-
अगर n सम है, तो c :=n / 2
-
अन्यथा जब n सम हो
-
यदि n 3 है या n/2 सम है, तो n को 1 से घटाएं अन्यथा n को 1 से बढ़ा दें
-
-
रिट को 1 से बढ़ाएं
-
-
वापसी सेवानिवृत्त।
उदाहरण (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