Đếm tất cả tiền tố của mảng nhị phân chia hết cho X trong C++

Trong hướng dẫn này, ta sẽ thảo luận chương trình để tìm số lượng tiền tố của mảng nhị phân chia hết cho X.

Cho một mảng nhị phân và giá trị X. Nhiệm vụ là tìm số lượng phần tử có tiền tố (dạng số nhị phân) chia hết cho X.

Ví dụ

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

int count_divx(int arr[], int n, int x) {
    int number = 0;
    int count = 0;
    for(int i = 0; i < n; i++) {
        number = number * 2 + arr[i];
        if(number % x == 0)
            count += 1;
    }
    return count;
}

int main() {
    int arr[] = {1, 0, 1, 0, 1, 1, 0};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 2;
    cout << count_divx(arr, n, x);
    return 0;
}

Kết quả

3