Single Number III
Problem Description
Given an integer array nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. You can return the answer in any order.
You must write an algorithm that runs in linear runtime complexity and uses only constant extra space.
Example 1:
Explanation: [5, 3] is also a valid answer.
Example 2:
Example 3:
Constraints:
- 2 <= nums.length <= 3 * 104
- -231 <= nums[i] <= 231 - 1
- Each integer in
numswill appear twice, only two integers will appear once.
Solve it on LeetCode
Approaches
1. HashMap
Intuition:
The simplest approach to solve this problem is to use a HashMap to count the occurrences of each number in the array. We then find the two numbers that appear exactly once by iterating through the map.
Code:
- Time Complexity: O(n): We iterate through the array and then through the map.
- Space Complexity: O(n): We use additional space for the HashMap.
2. Bit Manipulation
Intuition:
A more optimal solution uses bit manipulation. First, XOR all numbers to find the XOR of the two unique numbers. Then, find a bit that is set (1) in the XOR result and use it to differentiate the two unique numbers.
Steps:
- XOR operation between two identical numbers will cancel each other out to 0.
- By XORing all numbers, every pair of identical numbers cancels out, leaving us with the XOR of the two unique numbers.
- A single set bit in the XOR result tells us which bit differentiates the two unique numbers.
- We can use this bit to separate numbers into two groups and find the two unique numbers by XORing within these groups.
Code:
- Time Complexity: O(n): We make a single pass to XOR all elements and another pass to separate them into groups and find results.
- Space Complexity: O(1): We use a constant amount of extra space beyond the input and output.