Tìm số Sparse tiếp theo trong C++

Giới thiệu

Cho số nguyên N. Tìm số Sparse nhỏ nhất lớn hơn N.

Số Sparse: Số mà biểu diễn nhị phân không có hai bit 1 liên tiếp. VD: 5 (101), 16 (10000).

Ví dụ minh họa

Đầu vào

N = 7

Đầu ra

8

Giải thích

Nhị phân của 8 là 1000 - là số Sparse nhỏ nhất > 7.

Phương pháp 1: Kiểm tra tuần tự - O(N log N)

Kiểm tra từng số từ N+1 trở đi cho đến khi tìm thấy số Sparse.

Chương trình minh họa

#include <iostream>
using namespace std;

bool isSparseNumber(int N) {
    int prevBit = 0;
    while (N != 0) {
        int currBit = N & 1;
        if (currBit == 1 && prevBit == 1) return false;
        prevBit = currBit;
        N >>= 1;
    }
    return true;
}

int findNextSparseNumber(int N) {
    while (true) {
        if (isSparseNumber(N)) return N;
        N++;
    }
    return -1;
}

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

Đầu ra

The number is 564
The next Sparse Number is 576

Phương pháp 2: Thao tác bit - O(log N)

Chuyển N thành nhị phân, duyệt từ LSB đến MSB. Khi gặp hai bit 1 liên tiếp: đặt cả hai thành 0, bit tiếp theo thành 1. Tiếp tục cho đến hết.

Ví dụ: N=52 (110100). Gặp "11" ở đầu → thành 1000000 = 64.

Chương trình minh họa

#include <iostream>
using namespace std;

int findNextSparseNumber(int N) {
    int spNum[32] = {0};
    int n = 0;
    while (N != 0) {
        spNum[n++] = N & 1;
        N >>= 1;
    }
    spNum[n] = 0; // bit bảo vệ
    
    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;
        }
    }
    
    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;
}

Đầu ra

The number is 564
The next Sparse Number is 576