Đếm số phần tử mảng chia hết cho k trong C++

Giới thiệu

Cho mảng số nguyên và số k, đếm số phần tử chia hết cho k (phần dư = 0).

Ví dụ

• arr = [4,2,6,1,3,8,10,9], k = 2 → Kết quả: 5 (4,2,6,8,10)
• arr = [3,2,9,15,0,8,10], k = 3 → Kết quả: 3 (3,9,15). Lưu ý: 0 chia hết cho mọi số.

Các cách tiếp cận

Cách 1: Duyệt đơn giản (Naive)

Duyệt mảng, đếm phần tử thỏa arr[i] % k == 0. Độ phức tạp O(n).

Cách 2: Sử dụng STL count_if (Hiện đại)

Sử dụng lambda với count_if từ .

Ví dụ triển khai (C++)

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

// Cách 1: Naive
int countDivisibleNaive(int arr[], int size, int k) {
    int count = 0;
    for (int i = 0; i < size; i++)
        if (arr[i] % k == 0) count++;
    return count;
}

// Cách 2: STL count_if
int countDivisibleSTL(vector<int> vec, int k) {
    return count_if(vec.begin(), vec.end(), [k](int x){ return x % k == 0; });
}

int main() {
    int arr[] = {4, 2, 6, 1, 3, 8, 10, 9};
    int k = 2;
    int size = sizeof(arr) / sizeof(arr[0]);
    
    cout << "Cach 1: " << countDivisibleNaive(arr, size, k) << endl;
    
    vector<int> vec = {4, 2, 6, 1, 3, 8, 10, 9};
    cout << "Cach 2: " << countDivisibleSTL(vec, k) << endl;
    
    return 0;
}

Đầu vào

[4,2,6,1,3,8,10,9], k=2

Đầu ra

5