Single Element in a Sorted Array

Easy
0/40
Average time to solve is 15m
profile
Contributed by
310 upvotes
Asked in companies
OlaLenskartAmazon

Problem statement

You are given a sorted array ‘arr’ of ‘n’ numbers such that every number occurred twice in the array except one, which appears only once.


Return the number that appears once.


Example: 
Input: 'arr' = [1,1,2,2,4,5,5]

Output: 4 

Explanation: 
Number 4 only appears once the array.


Note : 
Exactly one number in the array 'arr' appears once.


Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘n’, representing the total number of elements present in the array 'arr'.
The next line contains ‘n’ single-spaced elements, representing the elements of the array 'arr'.


Output Format : 
The only line contains the integer denoting the number that appears once in the array.


##### 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 3 5 5


Sample Output 1 :
3


Explanation of Sample Input 1 :
Given array is [1, 1, 3, 5, 5]    
Here, 3 occurs once in the array. So, the answer is 3.


Sample Input 2 :
5
1 1 4 4 15


Sample Output 2 :
15


Explanation of Sample Input 2 :
The array is [1, 1, 4, 4, 15].    
Here, 15 occurs once in the array. So, the answer is 15.


Expected Time Complexity:
Try to solve this in O(log(n)).


Constraints :
1 <= n <= 10^5
0 <= arr[i] <= 10^9

Time Limit: 1 sec
Hint

Use the fact that the array is sorted and for each element of the array, check if it is Shizuka’s lucky number.

Approaches (4)
Brute force

The idea here is to use the fact that the array is sorted and the element of the array (‘arr[i]’) is unique if it doesn't have an adjacent element that has the same value as ‘arr[i]’. 

 

Algorithm:

  • If the length of the array equal to 1 then return ‘arr[0]’.
  • Declare a variable ‘answer’ to store Shizuka’s lucky number.
  • Run a loop from i = 0 to the length of the array - 1.
  • If ‘arr[i]’ does not have an adjacent element that is equal to ‘arr[i]’ then set ‘answer’ as ‘arr[i]’.
  • If the last two elements of the array are not equal then assign the last element of the array to the answer.
  • Finally, return the ‘answer’.
Time Complexity

O(N), where ‘N’ is the total number of elements in the given array. 

 

We are running a single loop here which takes O(N) time in the worst case.

Space Complexity

O(1). 

 

No extra space is being used.

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Single Element in a Sorted Array
Full screen
Console