Blog Logo
Research Scientist @ Foundation AI
·
read
Image Source: https://www.pixelstalk.net/mathematics-hd-desktop-wallpapers/
· · ·

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

· · ·