1def assert_equal(x, y)
 2  raise [x, y].inspect unless x == y
 3end
 4
 5class Solution
 6  # time: O(n)
 7  # space: O(n)
 8  def self.run(items)
 9    cache = Hash.new { |h, k| h[k] = 2 }
10
11    for i in items
12      cache[i] -= 1
13    end
14
15    cache.values.find { |value| value > 0 }
16  end
17
18  # time: O(n)
19  # space: O(1) assumes non negative numbers
20  def self.run(items)
21    cache = Array.new(items.size, 2)
22
23    for i in items
24      cache[i] -= 1
25    end
26
27    for i in (0...items.size)
28      return i if cache[i] % 2 != 0
29    end
30  end
31end
32
33assert_equal 1, Solution.run([4, 3, 2, 4, 1, 3, 2])
34puts 'Yay!'