[Arrays][InterviewBit] Find the duplicate

Find the duplicate

Question:

Given an array of n elements which contains elements from 0 to n-1, with any of these numbers appearing any number of times. Find these repeating numbers in O(n) time and using only constant memory space. 

Here  is the link

 Solution:

So basically you can't use a hashSet initially. So we have to find some way so that the number of checked elements are decreased.

Buckets! These days they are everywhere. We can create equal

  sized buckets here too, and limit the search to a single bucket. What should be the size of such a bucket? If $ \delta = (MAX-MIN)$, and there are $n$ elements, then we can create each bucket of size $$\frac{n}{\delta}$$. But this too will be a $O(n)$ search, so let's do something better.

We can decide to use buckets of size $\sqrt{n}$. 

Now the plan.

We can have $\sqrt{n}$ buckets. While going through all the elements we are given, we can check which bucket it belongs, and then increase the size  of that  bucket. Now the bucket that overlaps will be the one which has the duplicate element. Now, use the hash set. Go again through all the elements and then put the ones in the range in the hash set. Boom. You're done. The element that was already in the hash set will be the duplicate element.

Corner case.

Now this is magical fucking information. When you'll implement this stuff,  you'll realize $\sqrt{n}$ is like never an integer. So you'll have to make an array of buckets of size $\lfloor \sqrt{n} \rfloor+1$ and you'll check if any bucket reaches $\lfloor \sqrt{n} \rfloor$. But there'll be a point when no such bucket will be found because the duplicate is in the last bucket, which doesn't even have a size near to $\sqrt{n}$, so boom you're done. Take care of this case and you'll be okay.

Here is the code: