Finding the Missing Number


题目

\(1\)\(100\)\(100\)个整数中,除了其中一个以外,其余数字都会按某种无序的顺序念给你听,每隔\(10\)秒念出一个。你头脑很好,但记忆力只是常人水平,而且在整个过程中不能做任何记录。你怎样才能确保在全部念完之后,判断出哪个数字没有被念到?

分析

做法是把听到的数字一路累加。

因为从\(1\)\(100\)的总和是

\[ 1+2+\cdots+100=100\times 50.5=5050,\]

所以当\(99\)个数全部报完之后,只要用\(5050\)减去你一路累计得到的总和,差就是那个没有报出的数。

也就是说,你并不需要记住哪些数出现过,只需要记住“到目前为止一共报了多少”。

还有一个更适合心算的小技巧:在累加过程中,其实连百位和千位都不必保留,只做模\(100\)的加法就够了。

因为

\[ 5050\equiv 50\pmod{100},\]

所以你每次只保留当前累计和的后两位。设最后得到的结果是\(r\),那么缺失的数就满足

\[ x\equiv 50-r\pmod{100}.\]

最后再把它调整到\(1\)\(100\)的范围内即可:如果\(50-r\)已经在这个范围里,就直接取它;如果不是,就用\(150-r\)。这样得到的就是所缺的那个数。

因此,最实用的方法是:一边听一边把报出的数累加,只记后两位;结束后用\(50\)\(150\)减去这个结果,就能得到缺失的数字。

Previous Next