본문 바로가기
개발/C, C++

유일한 수

by 피로물든딸기 2021. 3. 1.
반응형

알고리즘 문제 전체 링크

 

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;
}
반응형

'개발 > C, C++' 카테고리의 다른 글

scanf로 문자열과 공백 받기  (0) 2021.03.16
소수 판단 함수  (0) 2021.03.14
C, C++ - 정수로된 FILE 입력  (1) 2021.03.14
유일한 수 두개  (0) 2021.03.01
C, C++ - 최하위 / 최상위 비트 구하기 (Find MSB, LSB)  (1) 2021.03.01

댓글