Single Number III
MedPrompt
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:
Input: nums = [1,2,1,3,2,5]
Output: [3,5]
Explanation: [5, 3] is also a valid answer.Example 2:
Input: nums = [-1,0]
Output: [-1,0]Example 3:
Input: nums = [0,1]
Output: [1,0]
Constraints:
2 <= nums.length <= 3 * 104-231 <= nums[i] <= 231 - 1- Each integer in
numswill appear twice, only two integers will appear once.
Approaches
2 approaches with complexity analysis and trade-offs.
Use a HashMap to store the frequency of each number in the array. Then iterate through the HashMap to find the two numbers with frequency 1.
Algorithm
- Create a HashMap to store number-frequency pairs
- Iterate through the array and count frequency of each number
- Iterate through the HashMap
- Find numbers with frequency 1 and add them to result array
- Return the result array
Walkthrough
This approach uses a HashMap to keep track of the frequency of each number in the array. We first iterate through the array and store the count of each number in the HashMap. Then, we iterate through the HashMap to find the two numbers that appear only once (frequency = 1).
public int[] singleNumber(int[] nums) { Map<Integer, Integer> map = new HashMap<>(); // Count frequency of each number for (int num : nums) { map.put(num, map.getOrDefault(num, 0) + 1); } int[] result = new int[2]; int index = 0; // Find numbers with frequency 1 for (Map.Entry<Integer, Integer> entry : map.entrySet()) { if (entry.getValue() == 1) { result[index++] = entry.getKey(); } } return result;}Complexity
Time
O(n) where n is the length of the input array
Space
O(n) to store the HashMap
Trade-offs
Pros
Easy to understand and implement
Works for any range of numbers
Cons
Does not meet the constant space requirement
Requires extra space proportional to input size
Use XOR operation to find the two unique numbers by first getting their XOR, then separating them based on a set bit in their XOR result.
Algorithm
- XOR all numbers to get XOR of two unique numbers
- Find rightmost set bit in the XOR result
- Use this bit to divide numbers into two groups
- XOR numbers in each group separately
- Return the two resulting numbers
Walkthrough
This approach uses the properties of XOR operation. When we XOR all numbers, we get the XOR of the two unique numbers (as all other numbers appear twice and get cancelled). Then, we find a set bit in this XOR result (as the two numbers are different, they must differ in at least one bit). We use this bit to divide all numbers into two groups, and XOR numbers in each group separately to get our two unique numbers.
public int[] singleNumber(int[] nums) { // Get XOR of all numbers int xorResult = 0; for (int num : nums) { xorResult ^= num; } // Find rightmost set bit in xorResult int rightmostSetBit = 1; while ((xorResult & rightmostSetBit) == 0) { rightmostSetBit <<= 1; } // Divide numbers into two groups and XOR int x = 0, y = 0; for (int num : nums) { if ((num & rightmostSetBit) != 0) { x ^= num; } else { y ^= num; } } return new int[]{x, y};}Complexity
Time
O(n) where n is the length of the input array
Space
O(1) as it uses only a constant amount of extra space
Trade-offs
Pros
Meets the linear time complexity requirement
Uses constant extra space
Efficient bit manipulation solution
Cons
Requires understanding of bit manipulation
May be less intuitive than other approaches
Solutions
Solution
public class Solution { public int[] SingleNumber(int[] nums) { int xs = nums.Aggregate(0, (a, b) => a ^ b); int lb = xs & -xs; int a = 0; foreach(int x in nums) { if ((x & lb) != 0) { a ^= x; } } int b = xs ^ a; return new int[] { a, b }; }}class Solution { public int [] singleNumber ( int [] nums ) { int xs = 0 ; for ( int x : nums ) { xs ^= x ; } int lb = xs & - xs ; int a = 0 ; for ( int x : nums ) { if (( x & lb ) != 0 ) { a ^= x ; } } int b = xs ^ a ; return new int [] { a , b }; } }/** * @param {number[]} nums * @return {number[]} */ var singleNumber = function (nums) { const xs = nums.reduce((a, b) => a ^ b); const lb = xs & -xs; let a = 0; for (const x of nums) { if (x & lb) { a ^= x; } } const b = xs ^ a; return [a, b]; };def lowbit ( x ): return x & ( - x ) # Example usage number = 12 # Binary: 1100 print ( lowbit ( number )) # Output: 4 (Binary: 100) number = 10 # Binary: 1010 print ( lowbit ( number )) # Output: 2 (Binary: 10) number = 18 # Binary: 10010 print ( lowbit ( number )) # Output: 2 (Binary: 10)class Solution { public: vector < int > singleNumber ( vector < int >& nums ) { long long xs = 0 ; for ( int & x : nums ) { xs ^= x ; } int lb = xs & - xs ; int a = 0 ; for ( int & x : nums ) { if ( x & lb ) { a ^= x ; } } int b = xs ^ a ; return { a , b }; } };Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.