Cho một chuỗi chỉ chứa '0' và '1', biểu diễn một số nhị phân đọc từ trái sang phải (ví dụ: "001" = 4, không phải 1). Mục tiêu là đếm số lượng chuỗi con biểu diễn số thập phân chẵn.
Quan sát quan trọng
Trong hệ nhị phân, một số là chẵn nếu và chỉ nếu bit cuối cùng (bit thấp nhất) là 0. Vì chuỗi đọc từ trái sang phải, bit cuối cùng của chuỗi con chính là ký tự cuối của chuỗi con đó.
Tuy nhiên, bài toán này có quan sát thú vị: nếu một chuỗi con bắt đầu bằng '0', thì giá trị thập phân của nó luôn chẵn. Điều này là do bit cao nhất (MSB) là 0, nên giá trị số thực chất là số nhị phân của phần còn lại, và bit cuối cùng của chuỗi con gốc quyết định tính chẵn/lẻ.
Cách tiếp cận đơn giản: Với mỗi vị trí i mà str[i] == '0', tất cả các chuỗi con bắt đầu từ i (có độ dài từ 1 đến len-i) đều cho giá trị chẵn. Số lượng chuỗi con như vậy là len - i.
Ví dụ minh họa
Ví dụ 1:
- Input: str = "101"
- Output: 2
- Giải thích: Các chuỗi con: "10"(2), "11"(3), "01"(1), "0"(0), "1"(1). Chỉ "01"(1?) và "0"(0) là chẵn. Kết quả 2.
Ví dụ 2:
- Input: str = "111"
- Output: 0
- Giải thích: Không có ký tự '0' nào, nên không có chuỗi con nào cho giá trị chẵn.
Mã nguồn C++
#include <bits/stdc++.h>
using namespace std;
int count_even(string str, int length) {
int count = 0;
for (int i = 0; i < length; i++) {
if (str[i] == '0') {
count += (length - i);
}
}
return count;
}
int main() {
string str = "00111";
int len = str.length();
cout << "So chuoi con nhi phan co gia tri chan: " << count_even(str, len) << endl;
return 0;
}
Kết quả chạy chương trình
So chuoi con nhi phan co gia tri chan: 9Độ phức tạp
- Thời gian: O(n) - chỉ duyệt một lần qua chuỗi.
- Không gian: O(1).
Giải thích kết quả "00111" = 9
Chuỗi: 0 0 1 1 1 (chỉ số 0-4)
- Tại i=0 ('0'): 5 chuỗi con ("0", "00", "001", "0011", "00111")
- Tại i=1 ('0'): 4 chuỗi con ("0", "01", "011", "0111")
- Tại i=2,3,4 ('1'): 0 chuỗi con
- Tổng: 5 + 4 = 9