개발/C, C++

유일한 수

피로물든딸기 2021. 3. 1. 21:47
반응형

알고리즘 문제 전체 링크

 

judge.koreatech.ac.kr/problem.php?id=1007

 

 

문제의 조건을 보면 홀수개의 숫자가 입력이 되고, 그 중 단 하나만 다르다.

따라서 bit 연산 ^(xor)을 누적하면 단 하나의 숫자만 남게 된다.

 

어떤 숫자 N에 숫자 M bit를 반전시키고, 다시 M bit를 반전 시키면 N이 되기 때문이다.

( N = N ^ M ^ M )

 

따라서 0부터 시작해서 누적하면 짝이 있는 숫자들은 자연스레 사라지게 된다.

#include <stdio.h>

int T, N;

int main(void)
{
	scanf("%d", &T);

	for (int tc = 0; tc < T; tc++)
	{
		int ans;
		
		scanf("%d", &N);
		
		ans = 0;
		for (int i = 0; i < N;i++)
		{
			int in;
			scanf("%d", &in);

			ans ^= in;
		}

		printf("%d\n", ans);
	}

	return 0;
}
반응형