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)
- Determine which integer is in the array twice
- 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:
sorting the array and then finding if the two elements are together. (avg case O(nlog(n)))
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?