use xor to find unique #

1 files changed, 28 insertions, 0 deletions

diff --git a/misc/find-non-duplicate-number/main.rb b/misc/find-non-duplicate-number/main.rb
new file mode 100644
index 0000000..0627b14
--- /dev/null
+++ b/misc/find-non-duplicate-number/main.rb
@@ -0,0 +1,28 @@
+#/usr/bin/env ruby
+
+def assert_equal(x, y)
+  raise [x, y].inspect unless x == y
+end
+
+def find_non_duplicate(items)
+  counts = Hash.new(0)
+
+  items.each do |item|
+    counts[item] += 1
+    if counts[item].even?
+      counts.delete(item)
+    end
+  end
+
+  counts.keys[0]
+end
+
+def find_non_duplicate(items)
+  result = 0
+  items.each do |item|
+    result = result ^ item
+  end
+  result
+end
+
+assert_equal(1, find_non_duplicate([4, 3, 2, 4, 1, 3, 2]))