Find The Single Element

Easy
0/40
Average time to solve is 10m
profile
Contributed by
207 upvotes
Asked in companies
AmazonStimVeda NeurosciencesSalescode.ai

Problem statement

You are given a sorted array 'arr' of positive integers of size 'n'.


It contains each number exactly twice except for one number, which occurs exactly once.


Find the number that occurs exactly once.


Example : 
Input: ‘arr’ = {1, 1, 2, 3, 3, 4, 4}.

Output: 2

Explanation: 1, 3, and 4 occur exactly twice. 2 occurs exactly once. Hence the answer is 2.
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line contains an integer ‘n’, representing the size of the array ‘arr’.

The second line contains ‘n’ integers, denoting the elements of the array ‘arr’.


Output Format: 
The output contains the integer in the array that occurs exactly once.


Note : 
You do not need to print anything; it has already been taken care of. Just implement the given function.
Sample Input 1:
5
1 1 2 2 3


Sample Output 1:
3


Explanation of sample output 1:
{1, 2} each occurs twice, whereas 3 occurs only once.
Hence the answer is 3.


Sample Input 2:
5
8 8 9 9 10


Sample Output 2:
10


Expected time complexity :
The expected time complexity is O(n), but try solving it in O(log n).


Constraints:
1 <= 'n' <= 10^4
1 <= 'arr[i]' <= 10^9

‘n’ is always odd.

Time Limit: 1 sec
Hint

Think of the most simple way to find out if there is another number equal to the current number in an array.

Approaches (6)
Brute Force

Approach:

We can iterate through the array and then for each element we find out if there is another element equal to the current element by iterating through the elements once again.

 

Algorithm:

  • for ‘i’ from 0 to ‘n - 1’:
    • pass = 0
    • for ‘j’ from 0 to ‘n - 1’:
      • if(i == j)
        • continue
      • if(arr[i] == arr[j])
        • pass = 1
    • if(pass == 0)
      • return arr[i]
Time Complexity

O(n ^ 2), where ‘n’ is the number of elements in the array ‘arr’.

We are iterating via ‘i’ from 0 to ‘n - 1’ and for each ‘i’, we are iterating via ‘j’ from 0 to ‘n - 1’, hence the overall time complexity of this solution is O(n ^ 2).

Space Complexity

O(1)

We are not utilizing any extra space, hence the overall space complexity of this solution is O(1).

Code Solution
(100% EXP penalty)
Find The Single Element
Full screen
Console