[학교 과제] 카드덱 (c++)

문제

1부터 N까지 정수가 쓰인 N장의 카드 중 1~2장의 카드가 빠졌다 

빠진 카드를 찾아라 (단 공간 복잡도는 O(1)의 공간 복잡도를 가져야 한다.)

빠지지 않은 카드의 번호는 무작위로 섞여 하나씩 제공된다.

풀이 방법

만약 카드가 1장 빠졌다면 1부터 N까지의 합(n*(n+1)/2) 에서 제공되는 카드수를 더 한 값을 빼면 빠진 카드의 수를 알 수 있다.

2장인 경우에는 식이 하나 더 필요하다 1부터 N까지의 제곱의 합이 필요하다 (n*(n+1)*(2n+1)/6) 에서 제공되는 카드의 수를 제곱한 것을 빼면 빠진 두 카드의 제곱의 합을 구 할수있다.

여기서 두 수를 더한 수의 제곱에서 두 카드의 제곱의 합을 빼면 수두의 2*곱한 값 을 알 수 있다.

두 수를 더한 값을 A 두수를 곱한 값을 B라고 하고 빠진 두 카드를 x,y 라고 하면 x = 루트((A^2 -4B) + A) / 2 로 알 수있다.