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 thoughts on “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

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