Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Problem of the day

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

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

Find the number that occurs exactly once.

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

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

```
The output contains the integer in the array that occurs exactly once.
```

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

```
5
1 1 2 2 3
```

```
3
```

```
{1, 2} each occurs twice, whereas 3 occurs only once.
Hence the answer is 3.
```

```
5
8 8 9 9 10
```

```
10
```

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

```
1 <= 'n' <= 10^4
1 <= 'arr[i]' <= 10^9
‘n’ is always odd.
Time Limit: 1 sec
```