Find odd-frequency element with O(1) space
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
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.
Overview: 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.
Read the full Amazon Software Engineer interview experience this question came from
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
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.
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.