Question : You are given an array . The array contains integer from 1 to n .The array contains n+1 numbers . Your task is to find the duplicate number.

Input: ar = [1,3,4,2,2]
Output: 2

Brute Solution :

The first thing that you can do is sort the array . Example : ar=[1,3,4,2,2] .
Now if we sort this array , it will look like this : arr=[1,2,2,3,4] .Now you can lineraly traverse the array , and check for one condition i.e. if your current integer is matching with index+1 or not , if it doesnot match , we got the answer .Condition looks like : if(ar[i]!=i+1) //answer
Pseudo Code :
sort(ar , ar+n)
for(i=0 to n-1){
if(ar[i]!=i+1)
{ //this is your answer }
}

Time complexity : O(nlogn)
Space complexity : O(1)

Optimal Solution :

Here we can bring a O(n) solution to find the duplicate number . We can traverse the array , and we will jump to the index using the current element.Say first element is 1 , we will move first index of the array only if our current element is positive, In this way we are going to multiply our elements with -1 . Once we reach our repeated number it will actually redirect us to a number which is already made negative , so we got our desired number . So , basically once you hit 2 , you will go to 2nd position of the array and make the element at 2nd position negative , Now again if we hit 2 , we will go to 2nd position but this time we will find that the element at second position is already negative , so we recieved our answer as 2.
So the condition :

if (nums[abs(nums[i])] >= 0)
nums[abs(nums[i])] = -nums[abs(nums[i])];
else
return abs(nums[i]);

Code :
function to find the duplicate :
C++ ;

int findDuplicate(vector<int>& nums) {
int size=nums.size();

    for (int i = 0; i < size; i++) {
    if (nums[abs(nums[i])] >= 0)
        nums[abs(nums[i])] = -nums[abs(nums[i])];
    else
        return  abs(nums[i]); }



return size+1;
}

Time complexity : O(n)
Space complexity : O(1)