配列に、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!