การแทนที่จำนวนเต็มใน C++

สมมติว่าเรามีจำนวนเต็มบวก 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

• รีเทิร์น.

ตัวอย่าง (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