Phần tử bằng tổng các phần tử còn lại trong mảng C++

Cho mảng arr[] n số nguyên dương. Tìm phần tử có giá trị **bằng tổng của tất cả các phần tử còn lại** trong mảng.

Ví dụ

Đầu vào: arr[] = {5, 4, 17, 1, 7}

Đầu ra: 17

Giải thích: Tổng các phần tử còn lại = 5+4+1+7 = 17.

Phương pháp giải - Toán học

Gọi tổng mảng là Sum. Phần tử cần tìm x thỏa: x = Sum - x => 2*x = Sum => x = Sum / 2.

Vậy chỉ cần tính tổng mảng, kiểm tra xem Sum có chẵn không, và xem giá trị Sum/2 có tồn tại trong mảng không.

Chương trình minh họa (O(N))

#include <iostream>
#include <unordered_set>
using namespace std;

int findElementEqualRestSum(int arr[], int n) {
    long long sum = 0;
    unordered_set<int> s;
    for (int i = 0; i < n; i++) {
        sum += arr[i];
        s.insert(arr[i]);
    }
    
    if (sum % 2 != 0) return -1; // Tổng lẻ không thể chia 2
    
    int target = sum / 2;
    if (s.count(target)) return target;
    return -1;
}

int main() {
    int arr[] = {5, 4, 7, 1, 17};
    int n = sizeof(arr) / sizeof(arr[0]);
    int res = findElementEqualRestSum(arr, n);
    if (res != -1) cout << "Phan tu thoa man: " << res;
    else cout << "Khong tim thay phan tu nao";
    return 0;
}

Đầu ra

Phan tu thoa man: 17