비트연산, Single Number

Problem

136. Single Number

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.

문제 해석

array의 요소들중 1번만 나타나는 값을 찾아서 반환해야 한다.

My Approach

HashMap을 이용하여 각 요소들을 count해서 1번만 count되는 수를 반환

문제점 : constant extra space를 사용해야 하는데 그 이상을 사용한다

문제 접근

XOR 비트 연산 n ^ n = 0

e.g.,) Input: nums = [4, 1, 2, 1, 2] looping around the size of the array

• 1st loop
  • num : 4 (int) -> 0100 (bit)
  • ret : 0 (int) -> 0000 (bit)
  • ret = num ^ ret -> 0100 (bit) -> 4 (int)
• 2nd loop
  • num : 1 (int) -> 0001 (bit)
  • ret : 4 (int) -> 0100 (bit)
  • ret = num ^ ret -> 0101 (bit) -> 5 (int)
• 3rd loop
  • num : 2 (int) -> 0010 (bit)
  • ret : 5 (int) -> 0101 (bit)
  • ret = num ^ ret -> 0111 (bit) -> 7 (int)
• 4th loop
  • num : 1 (int) -> 0001 (bit)
  • ret : 7 (int) -> 0111 (bit)
  • ret = num ^ ret -> 0110 (bit) -> 6 (int)
• 5th loop
  • num : 2 (int) -> 0010 (bit)
  • ret : 6 (int) -> 0110 (bit)
  • ret = num ^ ret -> 0100 (bit) -> 4 (int)

결국 single element만 남게 된다

XOR 비트연산 구현

class Solution {
	public int singleNumber(int[] nums) {
		int ret = 0;
		for(int num : nums) {
			ret ^= num;  // ret = ret ^ num;
		}
		return ret;
	}
}