Duplicate element in array

Question

This is kind of related to this question, but a little tweaked . We are given an array containing integers between 1 and 1000. Every integer from 1 and 1000 is in the array once, but one is in the array twice. (i.e. I remove a unique element from the list and introduce a duplicate element which is already in the list,remember the size of the array is still 1000)

1. Determine which integer is in the array twice
2. Can you do it while iterating through the array only once?

In the link that i have posted it's a different question altogether.

My Solution:

1. sorting the array and then finding if the two elements are together. (avg case O(nlog(n)))

2. Create a bit-array with a 1000 bits (won't take much memory). with 0 stored in each of the bit field. Iterate through the array of 1000 elements and flip the bit sign in the bit-array's index with the value of the array .

i.e. (if the 0th position of the array stores the value 548, we flip the 548th bit in the bit-array to 1).

The field with already flipped as 1 will be the repeated element

Solution2 iterates the array only once.

Now, I was reading about the 'Telescoping series', i haven't understood it fully. but is there a concept in there (or in discrete math) where we can just sum something and subtract with something else to get the duplicate number?

Answer 1

Calculate the sum of the array let it be S and let the repeated element be x. The repeated element can be determined by taking the difference between S and the sum of the array without the repeated element: x=S- (1000*(1001))/2.

Answer 2

Let's say, the x was replaced by y. The summation method tells that

y - x = sum_actual - sum_expected

Of course you can't deduce two variables from a single equation; you need another. Calculate the sum of squares:

   y^2 - x^2 = sum_squares_actual - sum_squares_expected

Now recall that sum of squares is n*(n+1)*(2*n + 1)/6

Answer 3

The sum of 1...1000 = 1001 * 500, and is therefore zero modulo 1001. Thus, finding the sum of the array modulo 1001 will give you the repeated element.

result = 0
for x in A:
    result = (result + x) % 1001

Answer 4

1000 is not that large. In addition to what other people have said, you could use a count array. For each number x you update the count count[x] = count[x] + 1 and check if this number is equal to 2.