Tìm phần tử lặp lại duy nhất từ ​​1 đến n-1 bằng C ++

Trong bài toán này, chúng ta được cung cấp một mảng không có thứ tự arr [] có kích thước N chứa các giá trị từ 1 đến N-1 với một giá trị xuất hiện hai lần trong mảng. Nhiệm vụ của chúng tôi là tìm phần tử lặp lại duy nhất từ ​​1 đến n-1 .

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

Đầu vào

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

Đầu ra

1

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

Một giải pháp đơn giản cho vấn đề là duyệt qua mảng và đối với mỗi giá trị, hãy tìm xem phần tử có tồn tại ở một nơi khác trong mảng hay không. Trả về giá trị với số lần xuất hiện kép.

Ví dụ 1

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

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

Đầu ra

The repetitive value in the array is 6

Một cách tiếp cận khác để giải quyết vấn đề là sử dụng thực tế là giá trị lặp lại trong mảng được tìm thấy bằng cách trừ tổng của tất cả các số nguyên từ 1 đến (N-1) khỏi tổng mảng.

Tổng của 1 ^st N-1 số tự nhiên (S _n ) =n * (n-1) / 2

doubleVal =arrSum - (S _n )

Ví dụ 2

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

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

Đầu ra

The repetitive value in the array is 6