Update appNew update is available. Click here to update.

Single Element in a Sorted Array

Last Updated: 29 Jan, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

Nobita wants to impress Shizuka by guessing her lucky number.

Shizuka gave Nobita a sorted list of ‘N’ numbers such that every number occurred twice in the list except Shizuka’s lucky number which appears only once.

Nobita asked Doraemon to help him but Doraemon doesn’t have a gadget that can find Shizuka’s lucky number.

So, Doraemon called you to find Shizuka’s lucky number. The fate of Nobita lies in your hand.

Note :

1. Shizuka’s lucky number will surely be present.
2. There will only be a single lucky number.
Input Format :
The first line contains a single integer ‘N’, representing the total number of elements present in Shizuka’s list.

The next line contains ‘N’ single-spaced elements, representing the elements of Shizuka’s list
Output Format :
Print an integer denoting the lucky number of Shizuka.
Constraints :
1 <= N <= 10^5
0 <= data <= 10^9

Where ‘data’ is the value of elements of Shizuka’s list. 

Time Limit: 1 sec
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.

Approach 1

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’.
Try Problem