[LeetCode] 260. Single Number III

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

leetcode - Single Number III

문제 유형 : 비트마스킹

문제 난이도 : Medium

 

문제

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.

 

정수 배열 nums가 주어진다.

두 개의 요소는 단 한번씩만 나오고, 나머지는 두 번씩 나온다.

당신은 한번씩만 나오는 요소들을 반환해야 한다.

순서는 상관없고,

선형 시간과 상수 공간 내로 해결하시오.

 

풀이

배열의 모든 요소를 xor하면, 두 개씩 있는 요소들은 없어지고, A xor B가 남는다.

A xor B의 최하위 1을 가진 비트 자릿수를 구한다. 이를 i번째자리라 하자.

A에는 i번째 자리에 1을 가지지 않은 그룹들을 xor시키고, B에는 i번째 자리에 1을 가진 그룹을들 xor시킨다.

두 쌍은 같은 그룹에 xor되므로, 상쇄된다.

결국, {A, B}가 최종적으로 남는다.

 

 

코드

C++

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int XOR = accumulate(nums.begin(), nums.end(), 0, bit_xor<>());

        int i = 0;
        while(((XOR >> i) & 1) == 0) i++;

        int A = 0, B = 0;
        for(int x : nums) {
            if(((x >> i) & 1) == 0) {
                A ^= x;
            } else {
                B ^= x;
            }
        }

        return {A, B};
    }
};

 

 

C++ - 변형 : LSB로 비교기준 삼기

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        // Step 1: XOR all numbers to get the XOR of the two unique numbers
        int XOR = accumulate(nums.begin(), nums.end(), 0, bit_xor<>());

        // Step 2: Find the least significant bit (LSB) that is set
        int LSB = XOR & -XOR;

        // Step 3: Partition the numbers based on the LSB and XOR within each partition
        int A = 0, B = 0;
        for (int x : nums) {
            if (x & LSB) {
                B ^= x;
            } else {
                A ^= x;
            }
        }

        return {A, B};
    }
};