Solve using cubic time

1 files changed, 30 insertions, 0 deletions

diff --git a/2020/08/24/main.rb b/2020/08/24/main.rb
new file mode 100644
index 0000000..102cf91
--- /dev/null
+++ b/2020/08/24/main.rb
@@ -0,0 +1,30 @@
+def assert(value)
+  raise value.inspect unless value
+end
+
+class Solution
+  # time: O(n^3)
+  # space: O(1)
+  def self.run(items)
+    for i in (0...items.size)
+      for p in (i+1...items.size)
+        for q in (p+1...items.size)
+          x = items[i] ** 2
+          y = items[p] ** 2
+          z = items[q] ** 2
+
+          return true if (x + y) == z
+        end
+      end
+    end
+
+    false
+  end
+end
+
+assert(Solution.run([3, 12, 5, 13]))
+assert(!Solution.run([1]))
+assert(!Solution.run([1, 2]))
+assert(!Solution.run([1, 2, 3]))
+assert(Solution.run([3, 4, 5]))
+puts "YAY!"