ตรวจสอบเลขฐานสองหาร 64 ลงตัว (ลบบิตได้) ใน C++

บทนำ

โจทย์: กำหนดสตริงเลขฐานสอง (Binary String) เราสามารถลบบิต (0 หรือ 1) ออกได้ ตรวจสอบว่าสามารถลบบิตบางส่วนเพื่อให้เลขที่เหลือหาร 64 ลงตัวได้หรือไม่

ข้อสังเกตสำคัญ

เลขฐานสองหาร 64 ลงตัว ⇔ ต้องลงท้ายด้วย 6 ศูนย์ (เพราะ 64 = 2⁶) และต้องมีบิต 1 อย่างน้อย 1 ตัว (เพื่อไม่ให้เป็น 0)

ขั้นตอนการแก้ปัญหา

รับสตริงเลขฐานสอง
นับจำนวน 0 จากท้ายไปหน้า
ถ้าพบ 0 ครบ 6 ตัว และยังมี 1 อยู่ด้านหน้า → ตอบ Yes
มิฉะนั้น → No

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

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

bool isBinaryStringDivisibleBy64(string binary_number, int n) {
    int zeroes_count = 0;
    for (int i = n - 1; i >= 0; i--) {
        if (binary_number[i] == '0') {
            zeroes_count++;
        }
        if (zeroes_count >= 6 && binary_number[i] == '1') {
            return true;
        }
    }
    return false;
}

int main() {
    string binary_string = "100100100100100";
    if (isBinaryStringDivisibleBy64(binary_string, 15)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

ผลลัพธ์

Yes

คำอธิบาย

สตริง "100100100100100" มี 0 ต่อท้าย 2 ตัว แต่มี 1 อยู่หน้า และมี 0 รวมมากกว่า 6 ตัว → สามารถเลือก 1 ตัวหน้าและ 0 6 ตัวท้ายได้ → ได้ 1000000₂ = 64₁₀

สรุป

โจทย์นี้ลดรูปได้เป็น: "มี 1 อยู่หน้า 0 อย่างน้อย 6 ตัวหรือไม่" ไม่ต้องสร้างสตริงย่อยจริงๆ