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

results matching ""

    No results matching ""