You are given an array of 1001 integers. The integers are in random order, but you know each of the integers is between 1 and 1000 (inclusive). Each number appears only once in the array, except for one number, which occurs twice. Assume that you can access each element of the array only once.
Task: In your language of choice, write an function to find the repeated number without using auxiliary storage.
Name:
Anonymous2008-05-12 15:12
I just wanted to use a double for loop ;_;
Name:
Anonymous2008-05-12 15:12
I WOULD USE A BUBBLE SORT
Name:
Anonymous2008-05-12 15:13
Sorting and scanning for two identical adjacent nodes?
Name:
Anonymous2008-05-12 15:14
Easy - sum them, then subtract 500500 (the sum of the integers from 1 to 1000) from that sum. This will be the missing number.
>>12
Since the function itself is data, you have to transcend.
Name:
Anonymous2008-05-12 15:23
>>13
Bob saget! I've been trolled by the parenthesiae
Name:
Anonymous2008-05-12 15:31
>>12 def foo(list): return 500500 - reduce(lambda x,y: x + y, list)
Name:
Anonymous2008-05-12 15:31
By the way, to sum any integers from 1 to n, simply multiply n by (n + 1) and divide the result by 2.
Name:
Anonymous2008-05-12 15:32
How can we solve this when you haven't specified which number occurs twice?!
And should the function find the first or the last occurence of the repeated number?
Name:
Anonymous2008-05-12 15:32
>>17
You mean to sum all integers from 1 to n inclusive.