[leetcode #136] Single Number

Problem

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

Input: nums = [2,2,1]
Output: 1

Example 2:

Input: nums = [4,1,2,1,2]
Output: 4

Example 3:

Input: nums = [1]
Output: 1

Constraints:

・ 1 <= nums.length <= 3 * 10⁴
・ -3 * 10⁴ <= nums[i] <= 3 * 10⁴
・ Each element in the array appears twice except for one element which appears only once.

Idea

주어진 배열 중 한 번만 등장하는 수가 무엇인지 구하는 문제다.

Map을 이용하면 쉽게 풀 수 있지만, Time Complexity: O(n), Space Complexity: O(1)로 풀라는 제약사항이 있다.

어렵게 생각하지 말고 간단하게 XOR 연산을 이용하면 금방 풀 수 있다. A XOR A = 0 이므로 모든 수를 XOR 연산했을 때 남는 수가 단 한 번만 등장하는 수가 된다.

Solution

class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;

        for (int num : nums) {
            res ^= num;
        }

        return res;
    }
}

Reference

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