Giới thiệu
Cho một chuỗi nhị phân, cho phép xóa các bit tùy ý. Kiểm tra xem có thể xóa một số bit để số còn lại chia hết cho 64 hay không.
Quan sát quan trọng
Số nhị phân chia hết cho 64 (2⁶) ⇔ 6 bit cuối cùng là 0.
Do có thể xóa bit tùy ý, ta chỉ cần: có ít nhất 1 bit '1' và sau nó có ít nhất 6 bit '0'.
Ví dụ
Chuỗi: "100100100100100" (15 bit)
Từ phải sang trái: đếm 6 bit 0 → tìm thấy bit 1 → Có thể tạo số chia hết cho 64
Mã nguồn hoàn chỉnh
#include <bits/stdc++.h>
using namespace std;
bool isBinaryStringDivisibleBy64(string binary_number, int n) {
int zeroes_count = 0;
// Duyệt từ phải sang trái (bit thấp đến bit cao)
for (int i = n - 1; i >= 0; i--) {
if (binary_number[i] == '0') {
zeroes_count++;
}
// Nếu đã có 6 bit 0 và gặp bit 1 → có thể tạo số chia hết 64
if (zeroes_count >= 6 && binary_number[i] == '1') {
return true;
}
}
return false;
}
int main() {
string binary_string = "100100100100100";
if (isBinaryStringDivisibleBy64(binary_string, binary_string.length())) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}
Kết quả chạy chương trình
Yes
Giải thích chi tiết
Với chuỗi "100100100100100":
Vị trí: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Bit: 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 Duyệt từ phải (i=14): i=14: '0' → zeroes=1 i=13: '0' → zeroes=2 i=12: '1' → zeroes=2 (chưa đủ 6) i=11: '0' → zeroes=3 i=10: '0' → zeroes=4 i=9: '1' → zeroes=4 i=8: '0' → zeroes=5 i=7: '0' → zeroes=6 i=6: '1' → zeroes=6 ≥ 6 VÀ bit='1' → TRUE
Phân tích độ phức tạp
- Thời gian: O(n) - duyệt chuỗi một lần
- Không gian: O(1) - chỉ dùng vài biến đếm
Mở rộng
Để kiểm tra chia hết cho 2ᵏ: cần ít nhất k bit 0 sau một bit 1.
Kết luận
Bài toán đơn giản hóa nhờ nhận ra bản chất của số chia hết cho lũy thừa của 2 trong hệ nhị phân. Chỉ cần đếm bit 0 từ cuối chuỗi.