New update is available. Click here to update.

Last Updated: 29 Jan, 2021

Difficulty: Easy

```
1. Shizuka’s lucky number will surely be present.
2. There will only be a single lucky number.
```

```
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
```

```
Print an integer denoting the lucky number of Shizuka.
```

```
1 <= N <= 10^5
0 <= data <= 10^9
Where ‘data’ is the value of elements of Shizuka’s list.
Time Limit: 1 sec
```

```
You do not need to print anything, it has already been taken care of. Just implement the given function.
```

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

The idea here is to store the frequency of elements of the array in a hashmap. Then we will traverse all elements of hashMap and the element whose frequency is 1 will be our answer.

Algorithm:

- Declare a hashMap to store the frequency of all elements of the array.
- Run a loop and store the frequency of each element of the array in the hashmap.
- Traverse all elements of hashMap and return the element whose frequency equal to 1.

The idea here is to use the fact that the bitwise xor of two numbers is zero. So, we will do the xor of all elements of the array, and all the numbers which occur twice get canceled out. So, in the end, we will get the number that occurs only once.

For example

Array = [1, 1, 3, 3, 5, 7, 7]

Here 1 ^ 1 ^ 3 ^ 3 ^ 5 ^ 7 ^ 7 = 5

As 1 ^ 1 = 3 ^ 3 = 7 ^ 7 = 0

Algorithm:

- Declare a variable ‘answer’ and initialize it with zero.
- Do xor of all elements and store the result in ‘answer’.
- Finally, return the answer.

The idea here is to use binary search and move left and right using the below observation.

- If mid is even, and arr[mid] == arr[mid + 1], then size of subarray [0...mid-1] (left side) is even (since the every element occurs twice), so left side does not contain the single occurrence element. Hence we need to check in [mid + 1, ..., N] subarray (right side of mid). Else we need to search for the required element on the left side.

Example:

[1, 1, 2, 2, 3(mid), 3, 5, 7, 7]

Here mid = 4. Here subarray[0…3] doesn’t contain our unique number. So we need to check in the right side of the mid i.e. subarray [5… 8]. - If mid is odd, and arr[mid] == arr[mid - 1], then the size of subarray [0...mid - 2] (left side) is even (since every element occurs twice), so the left side does not contain the single occurrence element. Hence we need to check in subarray [mid + 1, ..., N] (right side of mid). Else we need to search for the required element on the left side.

Example

[1, 1, 2, 2, 3, 3(mid), 5, 7, 7]

Here mid = 5. Here subarray[0…3] doesn’t contain our unique number. So we need to check in the right side of mid i.e. subarray [6… 8].

Algorithm:

- Declare three variables ‘low’, ‘high’, and ‘mid’ to use binary search and initialize ‘low’ with zero and ‘high’ with ‘n – 1’. Here ‘n’ is the length of the given array.
- Run a loop until low<high.
- Calculate ‘mid’ as mid = (low + high)/2
- If ‘mid’ is odd and ‘arr[mid]’ equals to ‘arr[mid - 1]’ or If mid is even and ‘arr[mid]’ equals to ‘arr[mid + 1]’ then do ‘low’ = ‘mid’ + 1 i.e. move right side.
- Else do high = mid i.e. move left side.
- Return ‘arr[low]’.

SIMILAR PROBLEMS

Search In A Sorted 2D Matrix

Posted: 23 Nov, 2022

Difficulty: Moderate

Ninja And The Strictly Increasing Array

Posted: 27 Nov, 2022

Difficulty: Moderate

Maximum GCD

Posted: 8 Dec, 2022

Difficulty: Hard

Negative To The End

Posted: 16 Dec, 2022

Difficulty: Easy

Fake Coin Problem

Posted: 24 Dec, 2022

Difficulty: Easy

Popular Interview Problems: