AlgorithmStudy/Problem/find_except_number at master · rangken/AlgorithmStudy · GitHub

Name		Name	Last commit message	Last commit date
parent directory ..
Makefile		Makefile
README.md		README.md
big_integer.java		big_integer.java
sample		sample
sample_out.c		sample_out.c
sum.java		sum.java
xor		xor
xor.c		xor.c
xor.java		xor.java

README.md

1~1억 개의 숫자중에 없는 숫자 찾기

알고리즘

방법1 : 1부터 1억까지의 숫자를 더한다음에 주어진 Test 값을 뺀다.
방법2 : 1억/2 값을 모두 뺀다음 더한다. 마지막에 N 에서 그값을 뺀다. 위에 내용과 똑같지만 오버플로우가 일어날 가능성이 좀더 줄어들긴함
방법3 : 1부터 1억까지 모두를 XOR 한다음에 주어진 Test 값을 XOR 한다.

실행

make sample
- sample.txt 테스트 데이터 1억개를 만든다.
make test1 (방법3)
- c 로만든 xor 방법(대략 10초)
make test2 (방법2)
- java의 BigInteger 를 사용해 오버플로우가 일어나지 않도록 한다. (대략 16초)
make test3 (방법3)
- java 로 구현한 XOR 방법(대략 12초)