Find duplicate
Given an array that has elements in the range 1..n. There is 1 duplicate element in it. Find the duplicate element using only O(1) space.
Example
i/p: 2,4,6,4,5,1,3
o/p: 4 => duplicate element
Solution
- Key here is to use the fact that there unique positions for each element except the duplicate.
- Hypothetically if we sort it then we can find the duplicate element. Lets achieve this using a counting approach.
- Use binary search technique, divide the problem into sub-problems at each step by counting which half has more elements than the number of positions.
- For example:
array: [2,4,6,4,5,1,3]
1st half: 2,4,6,4
2nd half: 5,1,3,7
1st half of a hypothetically sorted array would be: 1,2,3
So we narrow our search in the first half of the array in the next iteration
Code
def find_duplicate(a)
low = 0
high = a.size - 1
mid = (low + high ) / 2
while (low < high)
expected_lower_count = mid - low
actual_lower_count = 0
a.each do |e|
actual_lower_count + = 1 if e < mid && e > low
if expected_lower_count > actual_lower_count
# Search in the first half
high = mid
else
# Search in the second half
low = mid
end
end
end
return mid
end