Kiểm tra mảng có phần tử bằng nửa tổng mảng trong C++

Cho mảng arr[] đã sắp xếp, giá trị duy nhất. Nhiệm vụ: kiểm tra mảng có phần tử nào bằng nửa tổng mảng không.

Mô tả: Tìm x trong mảng sao cho tổng tất cả phần tử = 2*x.

Ví dụ:

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

Đầu ra: No

Giải thích: Tổng = 24. Không có phần tử nào *2 = 24.

Phương pháp giải

Tính tổng mảng. Nếu tổng lẻ => không có. Nếu chẵn, tìm x = tổng/2 bằng tìm kiếm nhị phân (vì mảng đã sắp xếp).

Chương trình minh họa

Ví dụ

#include <iostream>
using namespace std;

int checkForElement(int array[], int n) {
    int arrSum = 0;
    for (int i = 0; i < n; i++)
        arrSum += array[i];
    if (arrSum % 2)
        return -1;
    int start = 0;
    int end = n - 1;
    while (start <= end) {
        int mid = start + (end - start) / 2;
        if ((2 * array[mid]) == arrSum)
            return array[mid];
        else if ((2 * array[mid]) > arrSum)
            end = mid - 1;
        else
            start = mid + 1;
    }
    return -1;
}

int main() {
    int array[] = { 4, 5, 6, 7, 9 };
    int n = sizeof(array) / sizeof(array[0]);
    int x = checkForElement(array, n);
    if (x != -1)
        cout << "Element found, value is " << x;
    else
        cout << "Element not found!";
    return 0;
}

Kết quả

Element not found!