นับซับสตริงฐานสองที่มีค่าทศนิยมเป็นเลขคู่ ใน C++

ได้รับสตริงที่ประกอบด้วย 0 และ 1 เท่านั้น แทนตัวเลขฐานสองอ่านจากซ้ายไปขวา (เช่น 001 คือ 4 ไม่ใช่ 1) เป้าหมายคือหาจำนวนซับสตริงที่แทนค่าทศนิยมเป็นเลขคู่

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

ในระบบฐานสอง ตัวเลขจะเป็นเลขคู่ก็ต่อเมื่อหลักสุดท้าย (LSB) เป็น 0 แต่เนื่องจากอ่านจากซ้ายไปขวา ดังนั้นตัวอักษรแรกของซับสตริง (str[0]) จะกำหนดค่า parity: ถ้าเป็น '0' ค่าทศนิยมจะเป็นเลขคู่ ถ้าเป็น '1' จะเป็นเลขคี่

ตัวอย่าง

อินพุต: str = "101"

เอาต์พุต: 2

คำอธิบาย: ซับสตริงที่เป็นไปได้: 10, 11, 01, 0, 1 ซึ่ง 01 = 2 และ 0 = 0 เป็นเลขคู่ 2 ตัว

อินพุต: str = "111"

เอาต์พุต: 0

คำอธิบาย: ไม่มีซับสตริงไหนเป็นเลขคู่

แนวทางการแก้ปัญหา

• วนลูป for ตัวแปร i จาก 0 ถึง len-1
• ถ้า str[i] == '0' ทุกซับสตริงที่เริ่มจาก index นี้จะเป็นเลขคู่ในทศนิยม
• เพิ่มตัวนับ count += (length - i) (จำนวนซับสตริงที่เริ่มจาก i)

ตัวอย่างโค้ด 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 << "Count of even decimal value substrings in a binary string are: " << count_even(str, len) << endl;
    return 0;
}

ผลลัพธ์

Count of even decimal value substrings in a binary string are: 9