Just No more free questions left!

Upgrade Now

Find a duplicate, Space Edition™.

We have an array of integers, where:

  1. The integers are in the range 1..n
  2. The array has a length of n+1

It follows that our array has at least one integer which appears at least twice. But it may have several duplicates, and each duplicate may appear more than twice.

Write a function which finds an integer that appears more than once in our array. (If there are multiple duplicates, you only need to find one of them.)

We're going to run this function on our new, super-hip Macbook Pro With Retina Display™. Thing is, the damn thing came with the RAM soldered right to the motherboard, so we can't upgrade our RAM. So we need to optimize for space!

We can do this in space.

We can do this in less than time, while keeping space.

We can do this in time and space.

We can do this without destroying the input.

Most algorithms double something or cut something in half. How can we rule out half of the numbers each time we iterate through the array?

You must log in with one click to view the rest.

Once you're logged in, you'll get free full access to this and 4 other questions.

You must log in with one click to view the rest.

Once you're logged in, you'll get free full access to this and 4 other questions.

space and time.

Tricky as this solution is, we can actually do even better, getting our runtime down to while keeping our space cost at . The solution is NUTS; it's probably outside the scope of what most interviewers would expect. But for the curious...here it is!

This function always returns one duplicate, but there may be several duplicates. Write a function that returns all duplicates.

You must log in with one click to view the rest.

Once you're logged in, you'll get free full access to this and 4 other questions.

What's next?

RUN
Code execution powered by Qualified.io

. . .