배열에 C++에서 배열 합계의 절반 값을 갖는 요소가 있는지 확인

이 문제에서는 정렬된 고유 값의 배열 arr가 제공됩니다. 우리의 임무는 배열에 값이 배열 합계의 절반인 요소가 있는지 찾는 것입니다. .

문제 설명: 배열 arr[]의 경우 배열의 모든 요소의 합이 2*X와 같도록 배열에서 요소 x를 찾아야 합니다.

문제를 이해하기 위해 예를 들어 보겠습니다.

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

출력: 아니요

설명:

합계 =2 + 4 + 5 + 6 + 7 =24

요소를 찾을 수 없습니다.

해결 방법:

문제를 해결하려면 배열의 모든 요소 합계의 절반인 요소를 찾기만 하면 됩니다.

알고리즘:

1단계: 배열의 모든 요소의 합을 찾습니다.

2단계: 합계 값이 홀수이면 -1을 반환합니다.

3단계: 합계 값이 짝수이면 x*2 =합계가 되도록 요소 x를 찾습니다.

4단계: 요소가 발견되면 1을 반환합니다.
5단계: 요소를 찾을 수 없으면 -1을 반환합니다.

요소를 검색하기 위해 이진 검색 알고리즘 을 사용할 수 있습니다. 정렬됩니다.

우리 솔루션의 작동을 설명하는 프로그램,

예시

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

출력 -

Element not found!