Prime Factorisation | O(𝑛²), O(𝑛) | 5.83%, 59.60%
Intuition\n Describe your first thoughts on how to solve this problem. \nThis problem involves finding the lowest common multiple (LCM) and the greatest common 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThis problem involves finding the lowest common multiple (LCM) and the greatest common divider (GCD) [or highest common factor (HCF)] of the entire array minus one or no elements. Our approach uses <ins>number theory</ins> by first doing **prime factorisation** on all numbers, then comparing using factors to find the LCM and GCD/HCF of the array, for each scenario when one element is removed, and when none is removed. We can then multiply the LCM and GCD/HCF to get the factor score of each scenario, which we take the max factor score as the final answer.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- Prime Factorization: For each number in `nums`, store its prime factors and their counts.\n- LCM Calculation: The LCM will be the product of all the factors.\n- GCD Calculation: The GCD will be the product of all the common factors.\n- Compute LCM and GCD for the entire array without exclusions, and for subsets where each element is excluded one at a time.\n- Calculate Factor Score: Multiply LCM and GCD for each subset, keeping the maximum result.\n# Complexity\n*where $n$ is length of the list `nums`*.\n- **Time complexity: O(\uD835\uDC5B\xB2)**\nDue to passing through all $$n$$ elements to calculate LCM and GCD for each subset, and calculating $$n$$ different subsets where a different element is excluded each time.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n- **Space complexity: O(\uD835\uDC5B)**\nFor storing frequency dictionaries of each element\u2019s prime factors.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n| Runtime    | Memory |\n| -------- | ------- |\n| **143** ms &#124; beats **5.83%** | **16.75** MB &#124; beats **59.60%**|\n```python3 []\nclass Solution:\n    def maxScore(self, nums: List[int]) -> int:\n        import math\n        from collections import Counter\n\n        n = len(nums)\n        if n == 0:\n            return 0\n        if n == 1:\n            return nums[0] ** 2\n\n        def get_factors(num):\n            freq_dict = Counter()\n            while num > 1:\n                if num < 4:\n                    freq_dict[num] += 1\n                    break\n                prime = True\n                for i in range(2, (num // 2) + 1):\n                    if num % i == 0:\n                        freq_dict[i] += 1\n                        num = num // i\n                        prime = False\n                        break\n                if prime == True:\n                    freq_dict[num] += 1\n                    break\n            return dict(freq_dict)\n\n        arr_of_freq_dict = []\n\n        for num in nums:\n            arr_of_freq_dict.append(get_factors(num))\n        # print(arr_of_freq_dict)\n\n        def LCM(arr_of_freq_dict, n, excluded_idx):\n            output = 1\n            mydict = {}\n            # print("arr",arr_of_freq_dict)\n            for i in range(n):\n                if i == excluded_idx:\n                    continue\n                for key in arr_of_freq_dict[i]:\n                    # print(i,": key",key)\n                    if key not in mydict or arr_of_freq_dict[i][key] > mydict[key]:\n                        mydict[key] = arr_of_freq_dict[i][key]\n                    # print(key, mydict[key])\n            # print(mydict, excluded_idx)\n            for key in mydict:\n                output *= key ** mydict[key]\n            return output\n\n        def GCD(arr_of_freq_dict, n, excluded_idx):\n            output = 1\n            start = True\n            for i in range(n):\n                if i == excluded_idx:\n                    continue\n                if start == True:\n                    mydict = arr_of_freq_dict[i].copy()\n                    start = False\n                    continue\n                tempdict = mydict.copy()\n                for key in tempdict:\n                    if key not in arr_of_freq_dict[i]:\n                        del mydict[key]\n                    else:\n                        if arr_of_freq_dict[i][key] < mydict[key]:\n                            mydict[key] = arr_of_freq_dict[i][key]\n            for key in mydict:\n                output *= key ** mydict[key]\n            return output\n\n        lcm, gcd = LCM(arr_of_freq_dict, n, n + 1), GCD(arr_of_freq_dict, n, n + 1)\n        score = lcm * gcd\n        # print(lcm,gcd)\n        for i in range(n):\n            this_lcm, this_gcd = LCM(arr_of_freq_dict, n, i), GCD(\n                arr_of_freq_dict, n, i\n            )\n            # print(this_lcm, this_gcd)\n            this_score = this_lcm * this_gcd\n            if this_score > score:\n                score = this_score\n\n        if n == 2:\n            return max(nums[0] ** 2, nums[1] ** 2, score)\n        return score\n```\n# Detailed Approach\n1. Prime Factorization Function (`get_factors()`):\n    - Calculates prime factors of each number `num` using trial division up to $\\sqrt{num}$.\n    - Stores results in a frequency dictionary for each number, storing all the frequency dictionaries (prime factors) in a list of frequency dictionaries `arr_of_freq_dict`.\n2. LCM Calculation (`LCM()`):\n    - Initializes an empty dictionary `mydict` to track the highest power of each prime factor across included elements.\n    - Skips the excluded index.\n    - For each factor in each number, updates `mydict` with the highest exponent of each prime.\n    - Multiplies all factors in `mydict` to get the LCM.\n3. GCD Calculation (`GCD()`):\n    - Initializes `mydict` with factors of the first non-excluded element.\n    - For each included element, finds the minimum exponent for overlapping prime factors between `mydict` and the element.\n    - Multiplies factors in `mydict` to get the GCD.\n4. Score Calculation:\n    - Computes the factor score (LCM $\\times$ GCD) for the full array.\n    - Iteratively excludes each element, calculates LCM and GCD to get its factor score, and tracks the maximum score.\n\n# Detailed Complexity Breakdown\n### Time Complexity: $O(\uD835\uDC5B^2)$\n1. Prime Factorization: \n    - Each number `num` in nums is factorized up to its square root, thus taking $O(\\sqrt{\\text{num}})$ time.\n2. LCM Function: \n    - Each LCM call, compares all $$n$$ elements\' prime factors, taking $O(n\u0393^{\u22121}(\\text{max(num})))$ = $O(n)$ time.\n    - *[see next section on detailed Space Complexity for more details on why number of prime factors $\u0393^{\u22121}(\\text{num})$ is constant.]*\n3. GCD Function: \n    - Similarly, each GCD call compares all $$n$$ elements\' prime factors, taking $O(n\u0393^{\u22121}(\\text{max(num})))$ = $O(n)$ time.\n    - *[see next section on detailed Space Complexity for more details on why number of prime factors $\u0393^{\u22121}(\\text{num})$ is constant.]*\n4. Score Calculation (Outer Loop):\n    - LCD and GCD and subsequently the factor score (product of LCM and GCD) is calculated for $n$ scenarios where each element is removed, taking $O(n)$ in the outer loop.\n\n### Space Complexity: $O(\uD835\uDC5B)$\n1. Prime Factor Dictionaries `arr_of_freq_dict`: \n    - We store prime factors for $n$ elements, thus taking $O(n\u0393^{\u22121}(\\text{max(num})))$ =  $O(n)$ space.\n        -  Note that each element `num` will have up to $\u0393^{\u22121}(\\text{num})$ factors which is the inverse factorial, which can be estimated to a constant.\n            - Eg. If $\\text{num} = 20!$, then number of factors = 20 ($20!=1\\times 2\\times ... \\times 20$). Note that its number of prime factors will be even less at 8 ($20!=2^{18}\\times3^8\\times5^4\\times7^2\\times11^1\\times13^1\\times17^1\\times19^1$). Hence, the number of prime factors per element can be treated as constant.\n2. LCM/GCD Temporary Dictionaries `mydict` :\n    - `mydict` is constant sized, as it takes up to $O(\u0393^{\u22121}(\\text{max(num})))$ =  $O(1)$ space to store prime factors.\n\n# Best, Worst, and Average Case Analysis\n### Time Complexity\nFor all cases, $n$ elements will be looped through to consider the exclusion of that element, and for each excluded element, $n$ other elements\' frequency dictionaries of prime factors will be used to compute the LCM and GCD. As we have established in the detailed space complexity section that the number of prime factors in a number can be estimated to be constant, all cases will be $O(n^2)$ time  for the overall computing of LCM and GCDs. What may vary is the time complexity for the initial prime factorisation step.\n1. Best-case: $O(n\\text{log}(\\text{num}) + n^2)$ = $O(n^2)$\n    - Each number is an exponent of 2, taking $\\log(num)$ time to break down to its prime factor.\n2. Worst-case: $O(n\\sqrt{\\text{num}} + n^2)$ = $O(n^2)$\n    - Each number is prime, and requires $\\sqrt{\\text{num}}$ time to determine it has no prime factor other than itself..\n3. Average-case: $O(n\\sqrt{\\text{num}} + n^2)$ = $O(n^2)$\n    - On average, each number has to go through a number of passes and divisions before it is broken down into its prime factor(s).\n### Space Complexity\n1. All cases: $O(n)$\n    - For all cases, all $n$ elements\' frequency dictionaries of prime factors are stored. In the best case, each number has minimal prime factors (eg. the number is a prime). In the worst case, each number has multiple prime factors. However, as we have established in the detailed space complexity section that the number of prime factors in a number can be estimated to be constant, all cases will be $O(n)$ space complexity for $n$ frequency dictionaries.\n### Summary\n| Scenario | Time Complexity | Space Complexity |\n| - | - | - |\n| Best Case | $O(n^2)$ | $O(n)$ |\t\n| Worst Case | $O(n^2)$ | $O(n)$ |\n| Average Case | $O(n^2)$ | $O(n)$ |\n***\nCheck out my solutions to other problems here! \uD83D\uDE03\n*https://leetcode.com/discuss/general-discussion/5942132/my-collection-of-solutions*\n***
['Math', 'Number Theory', 'Python3']