หา Sparse Number ถัดไปด้วย C++

ภาพรวมปัญหา

Sparse Number: จำนวนที่ในรูปแบบไบนารีไม่มี 1 ติดกัน

ตัวอย่าง: 5 (101), 16 (10000)

ได้รับ N หา Sparse Number ที่น้อยที่สุดและ > N

ตัวอย่าง

อินพุต

N = 7

เอาต์พุต

8

คำอธิบาย

8 ในไบนารีคือ 1000 (ไม่มี 1 ติดกัน)

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

วิธีที่ 1: Brute Force - ตรวจสอบทีละตัว

วิธีที่ 2: Bit Manipulation - O(log N) ⭐

แปลง N เป็นไบนารี แล้วแก้ไขบิตที่มี 1 ติดกัน:

1. 掃จาก LSB ไป MSB
2. เจอ "11" ติดกัน → เปลี่ยนทั้งคู่เป็น "00" และเพิ่ม 1 ไปที่บิตถัดไป
3. ทำซ้ำจนไม่มี 1 ติดกัน

ตัวอย่าง: N=52 (110100)

เจอ 11 ที่บิต 5,4 → เปลี่ยนเป็น 00 และเพิ่ม 1 ที่บิต 6
ได้ 1000000 = 64

โค้ดตัวอย่าง (Bit Manipulation)

#include <iostream>
using namespace std;

int findNextSparseNumber(int N) {
    int spNum[32] = {0};
    int n = 0;
    
    // แปลงเป็นไบนารีเก็บในอาร์เรย์ (LSB first)
    while (N != 0) {
        spNum[n] = (N & 1);
        n++;
        N >>= 1;
    }
    n++;  // พื้นที่สำหรับ carry
    
    int lastCorrectedBit = 0;
    for (int i = 1; i < n; i++) {
        if (spNum[i] == 1 && spNum[i-1] == 1 && spNum[i+1] != 1) {
            spNum[i+1] = 1;
            for (int j = i; j >= lastCorrectedBit; j--)
                spNum[j] = 0;
            lastCorrectedBit = i + 1;
        }
    }
    
    // แปลงกลับเป็น decimal
    int sparseNumber = 0;
    for (int i = 0; i < n; i++)
        sparseNumber += spNum[i] * (1 << i);
    
    return sparseNumber;
}

int main() {
    int N = 564;
    cout << "The number is " << N << endl;
    cout << "The next Sparse Number is " << findNextSparseNumber(N);
    return 0;
}

เอาต์พุต

The number is 564
The next Sparse Number is 576

สรุป

Bit Manipulation เร็วกว่ามาก เหมาะสำหรับ N ใหญ่มาก