Python | Math (gcd)
Intuition\n\nThe initial distribution and order of symbols are irrelevant as they can be arbitrarily modified for $n \ge 2$ (and the answer is always positive f
# Intuition\n\nThe initial distribution and order of symbols are irrelevant as they can be arbitrarily modified for $n \\ge 2$ (and the answer is always positive for $n = 1$). Therefore, only the overall frequencies of all symbols are significant. \n\n# Approach\n\nTo distribute one letter evenly, we need the number of words to divide its frequency. We can combine these conditions for all symbols by requiring the number of words to be a _common divisor_ of all letter frequencies.\n\nEvery common divisor of a collection of numbers divides the _greatest common divisor_ of these numbers (and vice versa: only divisors of the gcd divide all numbers).\n\nThis approach is marginally faster than checking all divisibilities for a case of highly repetitive letter frequencies. However, we cannot short-circuit its evaluation.\n\n# Complexity\n\nHere $n$ is the number of words, $m$ is the maximum word length, and $k$ is the alphabet size (26).\n\n- Time complexity: $O(n \\cdot m)$ because I treat all math operations on small numbers as constant time.\n\n- Space complexity: $O(\\min(n \\cdot m, k))$ because the frequency map size is bounded from above by both quantities.\n\n# Code\n\n```python []\nclass Solution:\n    def makeEqual(self, A: list[str]) -> bool:\n        return gcd(*Counter(\'\'.join(A)).values()) % len(A) == 0\n```
['Hash Table', 'Math', 'String', 'Number Theory', 'Python3']