Find a Duplicate Item In an Array of Shuffled Consecutive Integers

16 Mar

Question: if you hava an array with n integers. These integers are in random order. And each interger is between 1 and n-1, including 1 and n-1. Additionally, there is one and only one integer, which appears twice, while all others only occur once. Find out the duplicate integer with O(n) time and O(1) space.

Solution of C programming language could be:

 And the Python solution (only include the core function) would be:

3 Replies to “Find a Duplicate Item In an Array of Shuffled Consecutive Integers

  1. Couldn’t you just use Gauss’s algorithm?
    Calculate what the sum of 1 … n-1 would be using 0.5*(n-1)*(n), then subtract this from the sum of all the ints in the input array and you should be left over the the duplicate number.

Leave a Reply to Ash Cancel reply

Your email address will not be published. Required fields are marked *

Please put your code into a <pre>YOUR CODE</pre> section. Thanks and Happy Coding!