CareerCup

#include<iostream>

using namespace std;

int main()
{
   int arr[] = {3, 1, 4, 4, 5, 2}; 
   int repeat = 0;
   for(int i = 0; i <= 5 ; i++)
   repeat = repeat^arr[i]^i;

  cout<<repeat;

}
Output:- 4

is there constraint on time complexity..?

1. Sort the array
2. Compare current element with next element, if they are same break the loop.

is there constraint on time complexity..?

1. Sort the array
2. Compare current element with next element, if they are same break the loop.

IF EXTRA SPACE is ALLOWED

use hashSet in java .

1. create a new hashSet HS
2. for every element in the array, check if hashSet contains the element (using HS.contains(element)) .
if the method returns False , then add the element in the hashSet .
3. Traverse next element in arrray and repeat step 2.

Space Complexity: O(n)
Time Complexity: O(n)

IF EXTRA SPACE IS NOT ALLOWED .
IF array elements are from 1 to N

Duplicate element = (Sum of array of elements) - (Sum of numbers from 1 to n)

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

We need to understand the question better. What is the significance of n=5? Does it mean that it will always have numbers from 1 to 5? if so, then sum of all digits from 1 to 5 = n(n+1)/2 = 15. And sum of the array is 19... 19-15 = 4.