We have an array of length 100, which contains numbers ranging from 0 and 99. There is exactly one duplicate number in this array. Write a program to find out this number.
I was asked this question yesterday during a phone interview. Like almost all phone interview questions, it appears to be simple. But there are actually several interesting
O(n) time solutions.