Tìm số lặp và số bị thiếu bằng cách sử dụng hai phương trình trong C ++

Trong bài toán này, chúng ta được cung cấp một mảng arr [] có kích thước N. Nó bao gồm các giá trị nguyên nằm trong khoảng từ 1 đến N. Và thiếu một phần tử x trong phạm vi trong khi một phần tử y trong mảng xảy ra nhân đôi. Nhiệm vụ của chúng tôi là tìm số lặp lại và số bị thiếu bằng cách sử dụng hai phương trình .

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

Đầu vào

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

Đầu ra

missing = 4, double = 3

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

Một phương pháp để giải quyết vấn đề là sử dụng hai phương trình cho hai giá trị x và y. Sau đó giải phương trình để nhận giá trị của x và y.

Hãy xem các phương trình và cách tạo chúng,

Tổng các phần tử của mảng bao gồm tổng của N số tự nhiên đầu tiên với một phần tử thừa và một phần tử thiếu.

arrSum = Sum(N) - x + y
y - x = arrSum - sum(N)

Đây là phương trình 1.

Bây giờ, chúng ta hãy tính tổng bình phương. Tương tự,

arrSumsq = sqSum(N) - x2 + y2
(y - x)*(y + x) = arrSumSq - sqSum(N)

Sử dụng phương trình 1,

x + y = (arrSumSq - sqSum(N)) / (arrSum - sum(N))

Thêm cả hai phương trình, chúng tôi nhận được

y = (arrSumSq - sqSum(N)) / (arrSum - sum(N)) + (arrSum - sum(N)) / 2

Sau đó, sử dụng giá trị của y, chúng ta sẽ tìm thấy x bằng cách sử dụng

x = y - (arrSum - sum(N))

Chúng tôi có công thức cho

sum(N) = n*(n-1)/2
sqSum(N) = n*(n+1)*(2n + 1)/ 6

arrSum là tổng của tất cả các phần tử của mảng

arrSumSq là tổng bình phương của tất cả các phần tử của mảng.

Ví dụ

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;
void findExtraAndMissingVal(int arr[], int n){
   int sumN = (n * (n + 1)) / 2;
   int sqSumN = (n * (n + 1) * (2 * n + 1)) / 6;
   int arrSum = 0, arrSqSum = 0, i;
   for (i = 0; i < n; i++) {
      arrSum += arr[i];
      arrSqSum += (arr[i]* arr[i]);
   }
   int y = (((arrSqSum - sqSumN) / (arrSum - sumN)) + sumN - arrSum) / 2;
   int x = arrSum - sumN + y;
   cout<<"The missing value from the array is "<<x;
   cout<<"\nThe value that occurs twice in the array is "<<y;
}
int main() {
   int arr[] = { 1, 2, 2, 3, 4 };
   int n = sizeof(arr)/sizeof(arr[0]);
   findExtraAndMissingVal(arr, n);
   return 0;
}

Đầu ra

The missing value from the array is 2
The value that occurs twice in the array is 5