Single Number Iii Solution for Wipro
Company: Wipro · Difficulty: Medium · Topics: Array, Bit Manipulation
Problem Statement
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.
Examples
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]
Approach
Bit Manipulation with XOR (Optimal)
1. XOR all numbers to get XOR of the two unique numbers
2. Find any set bit in the XOR result (rightmost set bit)
3. Divide numbers into two groups based on this bit
4. XOR each group separately to get the two unique numbers
Time and Space Complexity
- Time Complexity: O(n) - Single pass through array
- Space Complexity: O(1) - Only using constant extra space