a similar but harder problem

一個數組有n+1個數，都在1到n之間，並且每個數至少出現一次（有一個數重複了），找出那個重複的數（隻能用constant memory）。

所有跟帖： 

• sum mod n -haha2000- ♂ (0 bytes) () 05/18/2009 postreply 09:52:57

• I asked a similar question in an interview. -亂彈- ♂ (162 bytes) () 05/18/2009 postreply 10:01:54

• you are definitely right... I need to fix it :) -dynamic- ♂ (0 bytes) () 05/18/2009 postreply 10:48:03

• fix of the problem -dynamic- ♂ (160 bytes) () 05/18/2009 postreply 10:51:26

• algorithmic complexity requirement? -haha2000- ♂ (103 bytes) () 05/18/2009 postreply 19:19:21

• can be done in linear time... -haha2000- ♂ (150 bytes) () 05/18/2009 postreply 19:42:41

• it takes a bit more than that -dynamic- ♂ (438 bytes) () 05/18/2009 postreply 19:55:29

• hmm，這個有意思：） -戲雨飛鷹- ♀ (0 bytes) () 05/18/2009 postreply 21:12:19

• 回複：it takes a bit more than that -utopian- ♂ (51 bytes) () 05/20/2009 postreply 17:23:11

• hashing needs linear memory as well. we want constant memory her -dynamic- ♂ (0 bytes) () 05/20/2009 postreply 17:28:12

• Pay attention to some key numbers. -亂彈- ♂ (0 bytes) () 05/20/2009 postreply 19:24:24

• 覺得在哪裏見過這個題目 -haha2000- ♂ (19 bytes) () 05/21/2009 postreply 07:24:10

• I don't think so. -亂彈- ♂ (0 bytes) () 05/21/2009 postreply 09:52:29

• 這題目是IMB ２００４ 一月的一個puzzle：） -戲雨飛鷹- ♀ (79 bytes) () 05/21/2009 postreply 12:22:12

• Yes, right! thanks! -haha2000- ♂ (0 bytes) () 05/22/2009 postreply 11:05:23

• solution -dynamic- ♂ (572 bytes) () 05/20/2009 postreply 21:41:18

• hmmm，佩服. "形狀像一個勺子", haha... -戲雨飛鷹- ♀ (0 bytes) () 05/21/2009 postreply 12:25:03

• 這個題目曾是微軟的麵試題目。但是沒有了數組'read only'的條件， -戲雨飛鷹- ♀ (75 bytes) () 05/21/2009 postreply 13:12:13