Tìm nếu mảng có một phần tử có giá trị bằng một nửa tổng mảng trong C ++

Trong bài toán này, chúng ta được cung cấp một dãy các giá trị duy nhất đã được sắp xếp. Nhiệm vụ của chúng ta là tìm nếu mảng có một phần tử có giá trị bằng một nửa tổng của mảng .

Mô tả sự cố: Đối với mảng arr [], chúng ta cần tìm phần tử x trong mảng sao cho tổng tất cả các phần tử của mảng bằng 2 * X.

Hãy lấy một ví dụ để hiểu vấn đề,

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

Đầu ra: Không

Giải thích:

Tính tổng =2 + 4 + 5 + 6 + 7 =24

Không tìm thấy phần tử nào.

Phương pháp tiếp cận giải pháp:

Để giải quyết vấn đề, chúng ta chỉ cần tìm các phần tử bằng một nửa tổng tất cả các phần tử của mảng.

Thuật toán:

Bước 1: Tìm tổng tất cả các phần tử của mảng.

Bước 2: nếu giá trị tổng là lẻ, trả về -1.

Bước 3: nếu giá trị tổng là chẵn, hãy tìm phần tử x sao cho x * 2 =sum.

Bước 4: nếu phần tử được tìm thấy, trả về 1.
Bước 5: nếu phần tử không được tìm thấy, trả về -1.

Để tìm kiếm phần tử, chúng tôi có thể sử dụng thuật toán tìm kiếm nhị phân vì nó được sắp xếp.

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

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

Đầu ra -

Element not found!