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