New update is available. Click here to update.

Topics

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

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