Duplicate in Array

 Problem statement

Question Link: Duplicate In Array

You are given an array ‘ARR’ of size ‘N’ containing each number between 1 and ‘N’ - 1 at least once. There is a single integer value that is present in the array twice. Your task is to find the duplicate integer value present in the array.

For example:

Consider ARR = [1, 2, 3, 4, 4], the duplicate integer value present in the array is 4. Hence, the answer is 4 in this case.

Note :

A duplicate number is always present in the given array.

Very Simple Approach:

ARR = [1, 2, 3, 4, 4]. Consider this example.

In question, they said that only one element from 1 to N-1 has occurred twice, and the rest are present only once. So if we calculate the sum from 1 to N-1, it is 10 in the example.

Now, if we calculate the sum of the ARR, which is 14, take the difference of the sum of the ARR by the sum of the numbers in 1 to N-1, which is the answer to the simple problem.

Code:

int findDuplicate(vector<int> &arr) 

{

   int size=arr.size();

   int sumOri=0;

   for(int i=1;i<size;i++){

       sumOri+=i;

   }

   int sumArr=0;

   for(int i=0;i<size;i++){

       sumArr+=arr[i];

   }

   return sumArr-sumOri;

    

}

I hope you will understand the solution completely.If not feel free to comment ...