260. Single Number III

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. 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 nums will appear twice, only two integers will appear once.

Intuition

Approach 1:
Hash map and count

Approach 2: Bit manipulation
Bascially,

The two numbers are not same, so they are going to differ by one position
So that bit will be set

So just divide in two groups based on thar bit

One can find the lowest different bit by
num & -num
where -num is twos complement
You can do this by right shift

Take xor of all group numbers and you get answer

Links

https://leetcode.com/problems/single-number-iii/description/

Video Links

https://www.youtube.com/watch?v=wPBKH1jy0_E&ab_channel=Codebix

Approach 1:

Bit MAnipulation

C++

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        long int x_or = 0;
        vector<int> ans(2,0);

        for(int i=0; i<nums.size(); i++)
            x_or ^= nums[i];

        long int lowest_bit_set = x_or & -x_or;

        for(auto &it: nums){
            if(it & lowest_bit_set)
                ans[1] ^= it;

            else
                ans[0] ^= it;
        }

        return ans;
    }
};

Approach 2:

C++

Approach 3:

C++

Approach 4:

C++

Similar Problems