## DEV Community is a community of 615,372 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Write better code: Day 4 - Duplicate Space Edition

Arjun Rajkumar Updated on ・1 min read

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!

-

This problem is from InterviewCake.

## Discussion (1)

Arjun Rajkumar

Used a version of binary search to do this..

Logic:

• Given that array is of range 1..n and of n+1 length. Atleast one is repeated - so number of unique integers is (n -1 + 1) = n
• E.g [3, 4, 6, 5, 4, 4, 2] -> length is 7 so range has to be 1..6 ; no of possible unique integers is (6-1 +1 = 6)
• The number of elements is always one greater than the number of unique possibilities.
• If we cut this in half - the condition should still hold true - so atleast one of those halves should have one more element that the number of unique possibilities.
• If the half you have chosen, does not have more elements than the number of unque possibilities, drop that half.
• If the half you have chosen, meets the condition, then cut it into two again.
• Repeat cutting in halves until you are left with just one item.
``````def space_edition(input_array)
lowest_range = 1
highest_range = input_array.length - 1

while (lowest_range < highest_range)

mid = (lowest_range + highest_range) /2

first_half_lowest_range = lowest_range
first_half_highest_range = mid

second_half_lowest_range = mid + 1
second_half_highest_range = highest_range

number_of_elements_in_first_half = 0
input_array.each do |number|
if number >= first_half_lowest_range && number <= first_half_highest_range
number_of_elements_in_first_half += 1
end

number_of_unique_possibilities_in_first_half = first_half_highest_range - first_half_lowest_range + 1

if number_of_elements_in_first_half > number_of_unique_possibilities_in_first_half
lowest_range, highest_range = first_half_lowest_range, first_half_highest_range
else
lowest_range, highest_range = second_half_lowest_range, second_half_highest_range
end
end

end

return lowest_range
end
``````

The problem asked for space efficiency, so we are doing this in-place without creating another array.
It has O[1] 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]