C ++を使用して、1からn-1までの唯一の反復要素を見つけます

この問題では、1からN-1までの値を含むサイズNの順序付けられていない配列arr []が与えられ、1つの値が配列内で2回発生します。私たちのタスクは、1からn-1の間の唯一の反復要素を見つけることです 。

問題を理解するために例を見てみましょう

入力

arr[] = {3, 5, 4, 1, 2, 1}

出力

1

ソリューションアプローチ

この問題の簡単な解決策は、配列をトラバースし、値ごとに、要素が配列内の別の場所に存在するかどうかを確認することです。二重に出現する値を返します。

例1

ソリューションの動作を説明するプログラム

#include <iostream>
using namespace std;
int findRepValArr(int arr[], int n){
   for(int i = 0; i < n; i++)
   for(int j = i+1; j < n; j++)
   if(arr[i] == arr[j])
      return arr[i];
}
int main(){
   int arr[] = { 5, 3, 2, 6, 6, 1, 4 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"The repetitive value in the array is "<<findRepValArr(arr, n);
   return 0;
}

出力

The repetitive value in the array is 6

この問題を解決する別のアプローチは、配列の合計から1から（N-1）までのすべての整数の合計を引くことによって配列の反復値が見つかるという事実を使用することです。

1 ^st の合計 N-1自然数（S _n ）=n *（n-1）/ 2

doubleVal =arrSum-（S _n ）

例2

ソリューションの動作を説明するプログラム

#include <iostream>
using namespace std;
int findRepValArr(int arr[], int n){
   int arrSum = 0;
   for(int i = 0; i < n; i++)
      arrSum += arr[i];
   int sn = (((n)*(n-1))/2);
   return arrSum - sn;
}
int main(){
   int arr[] = { 5, 3, 2, 6, 6, 1, 4 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"The repetitive value in the array is "<<findRepValArr(arr, n);
   return 0;
}

出力

The repetitive value in the array is 6