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

ให้จำนวนเต็มบวก n ทำการดำเนินการ:

• ถ้า n คู่ → n = n/2
• ถ้า n คี่ → n = n+1 หรือ n = n-1

ตัวอย่าง: 7 → 4 (7→8→4→2→1 หรือ 7→6→3→2→1)

ขั้นตอนการแก้ปัญหา (Greedy + Bit Manipulation)

1. ret = 0, ใช้ long long กัน overflow
2. วนจน n > 1:
   • ถ้า n คู่ → n >>= 1
   • ถ้า n คี่:
     • ถ้า n == 3 หรือ (n >> 1) & 1 == 0 (บิตถัดไปเป็น 0) → n--
     • มิฉะนั้น → n++
   • ret++
3. คืน ret

เหตุผล: ต้องการให้ได้ 0 ติดกันมากที่สุดเพื่อหาร 2 เร็วขึ้น ยกเว้น n=3 ที่ -1 เร็วกว่า

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;
typedef long long lli;

class Solution {
public:
    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;
    }
};

int main() {
    Solution ob;
    cout << ob.integerReplacement(7);
}

Input

7

Output

4