Blogs

Finding duplicate element in less than O(n) extra space: A simple problem with countless insights.

The problem can be stated as:

Given an integer-array of size n+1, containing numbers from 1 to n. There is one element repeated, find duplicate element in O(n) time and in less than O(n) space.

The problem can be stated as:

Given an integer-array of size n+1, containing numbers from 1 to n. There is one element repeated, find duplicate element in O(n) time and in less than O(n) space.

Some observations:

• If space allowed was O(n), this problem could be solved with integer arrays (since, elements are from 1 to n, and n+1 being array size, A[i] can be used for counter and when it reaches 2 for some element, that's our answer.)
• Using a map also requires O(n) size.

My first attempt:

It's just a hack I believe, that I resorted to a bitset, instead of an array. Since for a number a, number of bits required is log a, for n such numbers, space required is O(n log n). What bitset does, is, you only need n bits for n numbers. Effectively space required is O(n / log n). And this hacky solution actually passed the system tests!

In pursuit of better solutions...

Attempt 2: "A duplicate means a cycle!"

for index set I = {0, 1, 2, ..., n} and A = {A[0], A[1], ..., A[n]}, let there is an edge between A[i] and i.