Find odd-frequency element with O(1) space
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Quick Answer: This question evaluates a candidate's understanding of frequency analysis and space-efficient algorithm design for identifying the uniquely odd-occurring value in an array.
Constraints
- 1 <= len(nums) <= 1000000
- -1000000000 <= nums[i] <= 1000000000
- Exactly one distinct value in nums appears an odd number of times
- All other distinct values appear an even number of times
Examples
Input: ([2, 3, 2, 4, 4],)
Expected Output: 3
Explanation: 2 appears twice and 4 appears twice, while 3 appears once, so 3 is the odd-frequency value.
Input: ([7],)
Expected Output: 7
Explanation: The single element appears once, which is odd.
Input: ([-1, 2, -1, 2, -1],)
Expected Output: -1
Explanation: 2 appears twice, while -1 appears three times. Negative integers work because XOR cancellation still applies.
Input: ([0, 5, 0, 5, 0],)
Expected Output: 0
Explanation: 5 appears twice, while 0 appears three times, so the answer is 0.
Input: ([10, 14, 10, 14, 14, 10, 10],)
Expected Output: 14
Explanation: 10 appears four times, while 14 appears three times.
Hints
- Think about an operation where combining a value with itself cancels it out.
- The bitwise XOR operation has useful properties: x ^ x = 0 and x ^ 0 = x.