Convert to Base -2 ใน C++

คำอธิบายปัญหา

กำหนดจำนวนเต็ม N ต้องการแปลงเป็นสตริงฐาน -2 (Base -2) ที่ประกอบด้วย '0' และ '1' เท่านั้น ไม่มีศูนย์นำหน้า (ยกเว้นกรณีเป็น "0")

ตัวอย่าง: 2 → "110" เพราะ (-2)² + (-2)¹ + (-2)⁰ = 4 - 2 + 1 = 3? รอสักครู่... 110 ในฐาน -2 = 1×(-2)² + 1×(-2)¹ + 0×(-2)⁰ = 4 - 2 + 0 = 2 ✓

17 → "10001" = 1×(-2)⁴ + 0 + 0 + 0 + 1×(-2)⁰ = 16 + 1 = 17

วิธีแก้ปัญหา

1. ถ้า N = 0 คืน "0"
2. วนลูปจนกว่า N จะเป็น 0:
3. rem = N % (-2)
4. N = N / (-2)
5. ถ้า rem < 0: rem += 2, N += 1 (ปรับเศษให้เป็นบวก)
6. เพิ่ม rem เข้าสตริงผลลัพธ์
7. กลับด้านสตริงก่อนคืนค่า

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

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

class Solution {
public:
    string baseNeg2(int N) {
        if(N == 0) return "0";
        string ret = "";
        while(N != 0) {
            int rem = N % (-2);
            N /= -2;
            if(rem < 0) {
                rem += 2;
                N++;
            }
            ret += to_string(rem);
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
};

int main() {
    Solution ob;
    cout << ob.baseNeg2(17);
    return 0;
}

อินพุต

17

เอาต์พุต

10001