Thay thế số nguyên trong C ++

Giả sử chúng ta có một số nguyên dương n và chúng ta có thể thực hiện các phép toán này như sau -

• Nếu n chẵn, thay n bằng n / 2.

• Nếu n lẻ, bạn có thể thay thế n bằng n + 1 hoặc n - 1.

Chúng ta phải tìm số lần thay thế tối thiểu cần thiết để n trở thành 1?

Vì vậy, nếu số là 7, thì câu trả lời sẽ là 4, như 7 → 8 → 4 → 2 → 1 hoặc 7 → 6 → 3 → 2 → 1

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• ret:=0, n:=x

• trong khi n> 1

  • nếu n chẵn thì c:=n / 2

  • ngược lại khi n chẵn

    • nếu n là 3 hoặc n / 2 chẵn thì giảm n đi 1, ngược lại tăng n lên 1

  • tăng ret lên 1

• trả lại ret.

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

7

Đầu ra

4