There are numbers from 1 to N in an array. out of these, one of the number gets duplicated and one is missing. The task is to write a program to find out the duplicate number. Conditions: you have to do it in O(n) time without using any auxilary space (array, bitsets, maps etc..)
I tried and then peeped at the solution provided at the site [by Sarin]. You can see the solution here. Nice one.
Filed under: Uncategorized
