Đếm phần tử có hiệu tuyệt đối với tổng các phần tử khác lớn hơn k trong C++

Cho một mảng số nguyên. Mục tiêu là đếm số phần tử thỏa mãn: hiệu tuyệt đối giữa tổng tất cả các phần tử và 2 lần phần tử đó lớn hơn k.

Công thức toán học

Gọi S = tổng tất cả phần tử. Với phần tử arr[i], tổng các phần tử khác arr[i] là S - arr[i].

Hiệu tuyệt đối: |(S - arr[i]) - arr[i]| = |S - 2×arr[i]| > k

Ví dụ minh họa

Ví dụ 1:

• Input: arr = {1,2,3,0,3,2,0,1}, k = 10
• Output: 2
• Giải thích: S = 12. Kiểm tra: |12-2×1|=10 (không >10), |12-2×2|=8, |12-2×3|=6, |12-2×0|=12 > 10. Chỉ 2 phần tử 0 thỏa mãn.

Ví dụ 2:

• Input: arr = {1,1,1,1,1}, k = 10
• Output: 0
• Giải thích: S = 5. Với mỗi 1: |5-2|=3 < 10.

Mã nguồn C++

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

int numberCount(int arr[], int n, int k) {
    int count = 0;
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += arr[i];
    }
    for (int i = 0; i < n; i++) {
        if (abs(sum - 2 * arr[i]) > k) {
            count++;
        }
    }
    return count;
}

int main() {
    int Arr[] = {1, 2, 3, 4};
    int len = sizeof(Arr) / sizeof(Arr[0]);
    int K = 5;
    cout << "So phan tu thoa man: " << numberCount(Arr, len, K);
    return 0;
}

Kết quả chạy chương trình

So phan tu thoa man: 2

Độ phức tạp

• Thời gian: O(n) - hai lần duyệt mảng.
• Không gian: O(1).

Lưu ý

• Sử dụng abs() từ <cmath> hoặc <cstdlib> cho số nguyên.
• Tránh tràn số khi S lớn: dùng long long cho biến sum.