Commit c0e62e1

@@ -14,6 +14,20 @@ class Solution
 
     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])