シャッフルされた連続した整数の配列から，重複する要素を見つけるには？

質問

最近、ある質問をどこかで見かけました。

1001個の整数からなる配列があるとします。整数の並びはランダムですが、それぞれの整数が1から1000（を含む）であることは分かっています。また、各数値は配列中に一度しか現れませんが、一度だけ現れる数値があります。配列の各要素に一度だけアクセスできると仮定する．繰り返される数を求めるアルゴリズムを記述しなさい．あなたのアルゴリズムで補助記憶装置を使用した場合、それを必要としないアルゴリズムを見つけることができますか？

私が知りたいと思っているのは の部分です。 であり、すなわち 補助記憶装置を使わず . 何か思い当たる節はありますか？

どのように解決するのですか？

全部足して、そこから1001個しか使わなかった場合の合計を引けばよいのです。

例えば

Input: 1,2,3,2,4 => 12
Expected: 1,2,3,4 => 10

Input - Expected => 2