This post originally appeared on Arjun Rajkumar's blog. Arjun is a web developer based in Bangalore, India.
Day 4: Question 1
Find a duplicate, Space Edition™.
We have an array of integers, where: The integers are in the range 1..n.
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 method 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 method 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!
If you want to follow along, feel free to post your answers in the comment.
My answers are in the comments.
This problem is from InterviewCake.
Top comments (1)
Used a version of binary search to do this..
The problem asked for space efficiency, so we are doing this in-place without creating another array.
It has O space, and O[logn] time as we used binary search (cutting in halves).
Note - there is a better way to improve this and reduce time to O[n]