Non-negative Integers without Consecutive Ones: จำนวนเต็มไม่ติดลบที่ไม่มี 1 ติดกันใน C++

ปัญหา

กำหนดจำนวนเต็มบวก n หาจำนวนจำนวนเต็มไม่ติดลบ ≤ n ที่ Binary Representation ไม่มี 1 ติดกัน

ตัวอย่าง: n = 7 (111₂) → จำนวนที่ถูกต้อง: 0(0), 1(1), 2(10), 4(100), 5(101) → 5 จำนวน

แนวคิด: Fibonacci + Digit DP บน Binary

ข้อสังเกต

จำนวน Binary String ความยาว L ที่ไม่มี 11 คือ Fib(L+2) (Fibonacci)

• L=1: 0, 1 → 2 = Fib(3)
• L=2: 00, 01, 10 → 3 = Fib(4)
• L=3: 000, 001, 010, 100, 101 → 5 = Fib(5)

Digit DP บน Binary (MSB to LSB)

1. แปลง n เป็น Binary String (MSB first)
2. Precompute zeroes[i], ones[i] = จำนวน valid strings ความยาว i+1 ที่ลงท้ายด้วย 0 หรือ 1
3. Scan จาก MSB ไป LSB:
   • ถ้าเจอ 11 → หยุด (invalid)
   • ถ้าเจอ 00 → ลบ ones[i] ออก (เพราะนับเกิน)

โค้ด C++

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

class Solution {
    string toBinary(int n) {
        string ret = "";
        while (n) {
            ret += char('0' + (n % 2));
            n >>= 1;
        }
        reverse(ret.begin(), ret.end());
        return ret.empty() ? "0" : ret;
    }
    
public:
    int findIntegers(int num) {
        string bits = toBinary(num);
        int n = bits.size();
        
        // zeroes[i] = จำนวน valid strings ความยาว i+1 ลงท้าย 0
        // ones[i]   = จำนวน valid strings ความยาว i+1 ลงท้าย 1
        vector<int> zeroes(n), ones(n);
        zeroes[0] = ones[0] = 1;  // length 1: "0", "1"
        
        for (int i = 1; i < n; i++) {
            zeroes[i] = zeroes[i-1] + ones[i-1];  // append 0
            ones[i] = zeroes[i-1];                // append 1 (ต้องตามด้วย 0)
        }
        
        int ret = zeroes[n-1] + ones[n-1];  // ทุก string ความยาว n
        
        // ปรับลดสำหรับ upper bound
        for (int i = n - 2; i >= 0; i--) {
            if (bits[i] == '0' && bits[i+1] == '0') {
                ret -= ones[i];  // นับเกิน strings ที่มี 11 ที่ตำแหน่ง i,i+1
            } else if (bits[i] == '1' && bits[i+1] == '1') {
                break;  // เจอ 11 แล้ว ไม่ต้องนับต่อ
            }
        }
        return ret;
    }
};

int main() {
    Solution ob;
    cout << ob.findIntegers(7);  // 5
    return 0;
}

การทำงานตัวอย่าง (n=7, binary=111)

ความซับซ้อน

• Time: O(log n) - ความยาว Binary
• Space: O(log n)

Input / Output

Input:  7
Output: 5