Which appears twice
Given an array where every number in the range 1...n appears once except for one number which appears twice. Write a function to find the number that appears twice.
Example
i/p: [1,2,3,4,5,6,6], 6
o/p: 6
Solution
- Use math instead of searching through the array
- Hint is that the numbers are in the range 1..n
- The difference between expected sum of the range and actual sum is the repeating number
Code
def which_appears_twice(array, n)
expected_sum = (n * (n+1))/2
sum = 0
array.each { |e| sum += e }
sum - expected_sum
end
Complexity
- O(n) to calculate sum of all numbers in the array
- O(1) extra space to hold expected sum