C++-এ ইন্টিজার রিপ্লেসমেন্ট

একটি ধনাত্মক পূর্ণসংখ্যা n দেওয়া আছে। আমরা নিচের অপারেশনগুলো করতে পারি:

• যদি n সম হয়, n-কে n/2 দিয়ে রিপ্লেস করুন।
• যদি n বিজোড় হয়, n-কে n+1 বা n-1 দিয়ে রিপ্লেস করতে পারেন।

n-কে ১ করার জন্য ন্যূনতম কতবার রিপ্লেসমেন্ট লাগবে তা বের করতে হবে। উদাহরণ: ৭ হলে উত্তর ৪, কারণ 7 → 8 → 4 → 2 → 1 বা 7 → 6 → 3 → 2 → 1।

সমাধানের ধাপগুলো:

• ret := 0, n := x
• n > 1 रहने পর্যন্ত:
  • যদি n সম হয়, n >>= 1।
  • অন্যथा যদি n বিজোড় হয়:
    • যদি n == 3 বা (n>>1) & 1 == 0 (অর্থাৎ n/2 সম), তবে n--, অন্যথায় n++।
  • ret++
• 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