Add solution for Project Euler 62

TheAlgorithms · dhruvmanila · Oct 15, 2020 · Oct 8, 2020 · Oct 8, 2020 · Oct 8, 2020
commit edc37bd3be9329beb1761c58f8c7c8041c86007b
diff --git a/DIRECTORY.md b/DIRECTORY.md
@@ -650,6 +650,8 @@
     * [Sol1](https://github.com/TheAlgorithms/Python/blob/master/project_euler/problem_551/sol1.py)
   * Problem 56
     * [Sol1](https://github.com/TheAlgorithms/Python/blob/master/project_euler/problem_56/sol1.py)
+  * Problem 62
+    * [Sol1](https://github.com/TheAlgorithms/Python/blob/master/project_euler/problem_62/sol1.py)
   * Problem 63
     * [Sol1](https://github.com/TheAlgorithms/Python/blob/master/project_euler/problem_63/sol1.py)
   * Problem 67

diff --git a/project_euler/problem_62/__init__.py b/project_euler/problem_62/__init__.py
diff --git a/project_euler/problem_62/sol1.py b/project_euler/problem_62/sol1.py
@@ -0,0 +1,50 @@
+"""
+Project Euler 62
+https://projecteuler.net/problem=62
+
+The cube, 41063625 (345^3), can be permuted to produce two other cubes:
+56623104 (384^3) and 66430125 (405^3). In fact, 41063625 is the smallest cube
+which has exactly three permutations of its digits which are also cube.
+
+Find the smallest cube for which exactly five permutations of its digits are
+cube.
+"""
+
+from collections import defaultdict
+
+def solution():
+    """
+    Iterate through every possible cube and sort the cube's digits in
+    ascending order. Sorting maintains an ordering of the digits that allows
+    you to compare permutations. Store each sorted sequence of digits in a
+    dictionary, whose key is the sequence of digits and value is a list of
+    numbers that are the base of the cube.
+
+    Once you find 5 numbers that produce the same sequence of digits, return
+    the smallest one, which is at index 0 since we insert each base in
+    ascending order.
+    """
+    freqs = defaultdict(list)
+    num = 0
+
+    while (True):
+        digits = get_digits(num)
+        freqs[digits].append(num)
+
+        if (len(freqs[digits]) == 5):
+            base = freqs[digits][0] ** 3
+            return base
+
+        num += 1
+
+def get_digits(num):
+    """
+    Computes the sorted sequence of digits of the cube of num.
+    """
+    cube = num ** 3
+    digits = [str(x) for x in str(cube)]
+    digits.sort()
+    return "".join(digits)
+
+if __name__ == "__main__":
+    print(solution())