ধরুন আমাদের একটি ধনাত্মক পূর্ণসংখ্যা 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> 1
-
যদি n জোড় হয়, তাহলে c :=n / 2
-
অন্যথায় যখন n জোড় হয়
-
যদি n 3 হয় বা n/2 জোড় হয়, তাহলে n 1 দ্বারা কমান, অন্যথায় n 1 দ্বারা বাড়ান
-
-
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
