def assert_equal(x, y)
  raise [x, y].inspect unless x == y
end

class Solution
  # time: O(n)
  # space: O(n)
  def self.run(items)
    cache = Hash.new { |h, k| h[k] = 2 }

    for i in items
      cache[i] -= 1
    end

    cache.values.find { |value| value > 0 }
  end

  # time: O(n)
  # space: O(1) assumes non negative numbers
  def self.run(items)
    cache = Array.new(items.size, 2)

    for i in items
      cache[i] -= 1
    end

    for i in (0...items.size)
      return i if cache[i] % 2 != 0
    end
  end
end

assert_equal 1, Solution.run([4, 3, 2, 4, 1, 3, 2])
puts 'Yay!'