← Back

👻 The Lonely Spirit Hunt

Find Unique Element (All Others Appear Twice)

Array Size

-

Mid Index

-

Mid Parity

-

Unique Found

?

Steps

0
🔑 Key Insight
Before the unique element: pairs start at even indices (0,1), (2,3)...
After the unique: pairs are shifted! Compare mid with mid^1 (XOR to get pair)
👻 Find the Lonely Spirit 👻
L: -
M: -
R: -
Generate an array to hunt the lonely spirit!

📖 Find Unique Element

Problem: Every element appears twice except one. Array is sorted. Find the unique.

Key: Use parity! Before unique: first of pair at even index. After unique: first at odd index.

Logic: If mid is even, check arr[mid] == arr[mid+1]. If true, unique is on right.

Time: O(log n)