ตรวจสอบว่าอาร์เรย์มีสมาชิกที่มีค่าเท่ากับครึ่งหนึ่งของผลรวมทั้งอาร์เรย์ใน C++

โจทย์

ได้รับอาร์เรย์ arr[] ที่เรียงแล้วและไม่ซ้ำ ทางเราต้อง ตรวจสอบว่ามีสมาชิก x ที่ 2*x = ผลรวมทั้งอาร์เรย์ หรือไม่

ตัวอย่าง

Input: arr[] = {2, 4, 5, 6, 7}

Output: No

อธิบาย: ผลรวม = 24, ไม่มีตัวเลขไหนคูณ 2 ได้ 24

แนวทางแก้ปัญหา

1. หาผลรวมทั้งอาร์เรย์
2. ถ้าผลรวมเป็นคี่ -> ไม่มีคำตอบ
3. ถ้าผลรวมเป็นคู่ -> หา sum/2 ด้วย Binary Search (เพราะอาร์เรย์เรียงแล้ว)

โปรแกรมตัวอย่าง

#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, 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;
}

ผลลัพธ์

Element not found!