Find hacky solution with O(1) space with some assumptions about data

1 files changed, 14 insertions, 0 deletions

diff --git a/2020/08/18/main.rb b/2020/08/18/main.rb
index efc2263..f5ffc9d 100644
--- a/2020/08/18/main.rb
+++ b/2020/08/18/main.rb
@@ -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])