You are given an integer array nums. In this array:
Exactly one element appears once.
Exactly one element appears twice.
All other elements appear exactly three times.
Return an integer array of length 2, where the first element is the one that appears once, and the second is the one that appears twice.
Your solution must run in O(n) time and O(1) space.
Example 1:
Input: nums = [2,2,3,2,5,5,5,7,7]
Output: [3,7]
Explanation:
The element 3 appears once, and the element 7 appears twice. The remaining elements each appear three times.
Example 2:
Input: nums = [4,4,6,4,9,9,9,6,8]
Output: [8,6]
Explanation:
The element 8 appears once, and the element 6 appears twice. The remaining elements each appear three times.
Constraints:
3 <= nums.length <= 105-231 <= nums[i] <= 231 - 1nums.length is a multiple of 3.Problem Overview: You are given an integer array where every value appears exactly twice except one value that appears only once. Return the element that occurs once. The challenge is to do it efficiently without extra memory.
Approach 1: Hash Map Frequency Count (O(n) time, O(n) space)
The straightforward solution counts how many times each number appears. Iterate through the array and store frequencies in a hash map. After building the map, scan through the entries and return the number with frequency 1. This approach is easy to implement and works for any frequency‑based problem, but it uses additional memory proportional to the array size.
Approach 2: Sorting the Array (O(n log n) time, O(1) extra space)
Another option is sorting the array first. Once sorted, identical values become adjacent. Iterate through the array in pairs: if nums[i] != nums[i+1], the current element is the one that appears once. If they match, skip both and continue. Sorting simplifies comparison logic but increases runtime to O(n log n). This approach works when modifying the array is acceptable.
Approach 3: Bit Manipulation with XOR (O(n) time, O(1) space)
The optimal solution relies on the XOR operation. XOR has two useful properties: a ^ a = 0 and a ^ 0 = a. If you XOR all elements in the array, every pair cancels itself out because identical numbers XOR to zero. Only the number that appears once remains in the final result. Iterate through the array and keep a running XOR value. The final accumulator is the answer.
This technique is common in problems involving duplicate cancellation and shows up frequently in bit manipulation interviews. It also works well with linear scans over an array, making it both memory‑efficient and fast.
Recommended for interviews: The XOR solution is what interviewers usually expect. It demonstrates understanding of bit operations and achieves optimal O(n) time with O(1) space. Starting with the hash map approach shows you understand the problem, but moving to the XOR optimization signals stronger problem‑solving skills and familiarity with bit manipulation patterns.
Solutions for this problem are being prepared.
Try solving it yourself| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Map Frequency Count | O(n) | O(n) | General solution when memory usage is not a concern and simplicity is preferred |
| Sorting | O(n log n) | O(1) | When modifying the array is allowed and you want a simple comparison-based approach |
| Bit Manipulation (XOR) | O(n) | O(1) | Optimal approach for large arrays and interview settings |
Practice Once Twice with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor