Coding questions · Amazon
Find odd-frequency element with O(1) space
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.
You're given an integer array where exactly one value appears an odd number of times and all other values appear an even number of times. Implement a function that returns the odd-frequency value. Follow-ups: a) Reduce extra space to O(1). b) Analyze time and space complexity. c) Explain correctness for large inputs and negative integers.
Find Odd-Frequency Element with O(1) Space
You are given a non-empty integer array nums. Exactly one distinct value appears an odd number of times, and every other distinct value appears an even number of times. Return the value that appears an odd number of times. Your solution should use O(1) extra space and should work for large inputs and negative integers.
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
Example 1
Input: ([2, 3, 2, 4, 4],)
Output: 3
Explanation: 2 appears twice and 4 appears twice, while 3 appears once, so 3 is the odd-frequency value.
Example 2
Input: ([7],)
Output: 7
Explanation: The single element appears once, which is odd.
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.