- Arrays, Searching, Sorting

Find the repeating element in an Array of size N consisting of first M natural numbers

Find the repeating element in an Array of size N consisting of first M natural numbersGiven an array arr[] of size N, which contains a permutation of numbers from 1 to M, as well as an element that is repeated(one or more times), the task is to find the repeating element.Examples:Input: arr[]={2, 6, 4, 3, 1, 5, 2}, N=7Output:2Explanation: In arr[], all elements from 0 to 6 occurs once, except 2 which is repeated once.Input: arr[]={2, 1, 3, 1, 1, 1}, N=6Output:1Naive Approach: The naive approach would be to sort the array and check for adjacent elements that are equal.Time Complexity: O(NlogN)Auxiliary Space: O(1)Approach: Follow the steps below to solve the problem:Initialize two variables M and sum to store the maximum element and the sum of the array respectively.Traverse array arr and do the following:Add the current element to sumCompare the current element to M to calculate the maximum element.Store the sum of permutation from 1 to M in a variable say, sum1, using the formula:Sum of elements from 1 to X= X*(X+1)/2Calculate the answer as the difference between sum and sum1 divided by the number of extra characters i.e. (sum-sum1)/(N-M).Below is the implementation of the above approach:C++#include using namespace std;int repeatingElement(int arr[], int N){            int M = 0, sum = 0;    for (int i = 0; i < N; i++) {                sum += arr[i];                M = max(M, arr[i]);    }        int sum1 = M * (M + 1) / 2;        int ans = (sum - sum1) / (N - M);    return ans;}int main(){        int arr[] = { 2, 6, 4, 3, 1, 5, 2 };    int N = sizeof(arr) / sizeof(arr[0]);        cout