남은 숫자

99개의 값을 저장할수 있는 배열 k[0], k[1], k[2], ... , k[98] 이 있다.

1부터 100까지의 값이 들어 있는 집합 {1, 2, 3, ..., 100}에서 무작위로 수를 꺼내어 배열에 저장했다.

집합에 들어 있는 원소의 수는 100개인 반면, 배열은 값을 99개까지만 저장할 수 있으므로 집합 안에 하나의 숫자가 남았다.

남은 것이 어느 수인지 확인할 수 있는 방법은?

 조금 오래된 문제이긴 하다. 하나하나 모두 해보는 방법으로 배열안에 숫자를 모두 확인하는 방법이 있지만, 컴퓨터에게 그리 적절한 방법은 아닌 듯 하다. 그리 어렵지 않으니 조금만 생각하면 답을 찾을 수 있을 것이다.

 우선, 1부터 100까지의 합은 (1+100)*50으로 5050이다.

한편, 배열에 모두 저장되고 숫자가 한개 남았다면 배열의 합을 모두 더한 값은 5050에서 그 남은 숫자 하나가 빠진 것 만큼일 것이다.

따라서 5050 - (배열안에 숫자들 합)을 하면 남은 한개의 숫자가 무엇인 알 수 있다.