How to find a duplicate element in an array of shuffled consecutive integers?

arrays algorithm duplicates
SysAdmin picture SysAdmin · Apr 9, 2010 · Viewed 64.4k times · Source

I recently came across a question somewhere:

Suppose you have an array of 1001 integers. The integers are in random order, but you know each of the integers is between 1 and 1000 (inclusive). In addition, 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. Describe an algorithm to find the repeated number. If you used auxiliary storage in your algorithm, can you find an algorithm that does not require it?

What I am interested in to know is the second part, i.e., without using auxiliary storage. Do you have any idea?

Answer

leppie picture leppie · Apr 9, 2010

Just add them all up, and subtract the total you would expect if only 1001 numbers were used from that.

Eg:

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

Input - Expected => 2

Related questions

Algorithm: efficient way to remove duplicate integers from an array

I got this problem from an interview with Microsoft. Given an array of random integers, write an algorithm in C that removes duplicated numbers and return the unique numbers in the original array. E.g Input: {4, 8, 4, 1, 1, 2, 9} Output: {4, 8, 1, 2, 9, ?, ?} One caveat is …

Read More
How do I check if an array includes a value in JavaScript?

What is the most concise and efficient way to find out if a JavaScript array contains a value? This is the only way I know to do it: function contains(a, obj) { for (var i = 0; i < a.length; i++) { …

Read More
Finding the max/min value in an array of primitives using Java

It's trivial to write a function to determine the min/max value in an array, such as: /** * * @param chars * @return the max value in the array of chars */ private static int maxValue(char[] chars) { int max = chars[0]; for (int ktr = 0; …

Read More