Thursday, November 1, 2012

Puzzle 4: Find the duplicate one out.

Puzzle 4: Suppose there are elements from 1,2,3......n-1 which is to be inserted in an array of size n in such a way that every element is inserted atleast once.
Now as per the Pigeonhole Principle definitely there must be one element which occur twice in the array.
Aim is to find the element and the index which is entered twice in complexity of O(n) and memory utilization can be O(log n)

NOTE: The elements can be entered in random ordered.

Hint: This puzzle will use the same approach which is being used in the previous puzzle 3

Solution: Let's take an example to solve the problem:
Array values: { 2,3,6,8,2,1,9,7,5,4}
Here also we will take 2 pointers one start from index 0 to n-1
And other will jump based on the current value at any index.
The generalize formula for p1 and p2 will be:
p1 = i where i ranges from i = 1 to n-1
p2 = Array[0] -> p2 = Array[Array[0]] and so on.

By doing so, once the value of p1 and p2 become equal then we found the faulty value with index.

Refer the following table to see how values of p1 and p2 varies for each iteration.

Output: p2 is the faulty node.
Note: If p1 reaches at end without exit condition then there is no duplicity at all. Which can't be case.