· · ·

### Q: Find duplicate in limited range (1 to n-1) array of size n using XOR operation.

#### Input:

```
a = [1, 2, 3, 4, 4]
```

#### Output:

```
4
```

#### Algorithms:

- Logic:
- XOR all the numbers
- XOR with all the numbers between 1 to n-1.
- a ^ a = 0
- 0 ^ 0 = 0
- a ^ 0 = a
- Complexity:
- Time: O(n)
- Space: O(1)

```
a = [1, 2, 3, 4, 4]
xor = 0
for elem in a:
xor = xor ^ elem
for i in range(len(a)):
xor = xor ^ i
print(xor)
```

## REFERENCES:

500 Data Structures and Algorithms practice problems and their solutions

Find a duplicate element in a limited range array

· · ·