JavaScript | sqrt(n) runtime with explanation | Math
Intuition\nThis task is an overcomplicated way of saying - find all n and m, such that:\n\n0 < n <= nums.length\n0 < m <= nums.length\nn * m = nums.length\n\nLe
# Intuition\nThis task is an overcomplicated way of saying - find all `n` and `m`, such that:\n\n`0 < n <= nums.length`\n`0 < m <= nums.length`\n`n * m = nums.length`\n\nLet\'s see how to solve this with an example.\nSuppose `nums.length` is $$24$$. There would be `8` valid combinations of $$n$$ and $$m$$.\n\n- $$1 * 24$$\n- $$2 * 12$$\n- $$3 * 8$$\n- $$4 * 6$$\n- $$6 * 4$$\n- $$8 * 3$$\n- $$12 * 2$$\n- $$24 * 1$$\n\nAnd since $$a * b = b * a$$ (math rule), eventually `n` and `m` values just swap. Therefore, we can just take the first `4` valid combinations and assume them to be valid twice (as $$n * m$$ and $$m * n$$).\n\nWhy 4?\nBecause $$n$$ and $$m$$ can only go as high as $$sqrt(nums.length)$$ for the equatins to be valid, which in this case is about $$4.9$$.\n\n# Code\n```\nfunction sumOfSquares(nums) {\n    const n = nums.length;\n\n    let result = 0;\n\n    for (let i = 1; i * i <= n; i++) {\n        if (n % i === 0) {\n            // This is the n * m combination\n            result += nums[i - 1] ** 2;\n\n            // This is the m * n combination\n            let div = n / i;\n            if (div !== i) result += nums[div - 1] ** 2;\n        }\n    }\n\n    return result;\n};\n```\n\n# Complexity\n- Time complexity: $$O(sqrt(n))$$\n\n- Space complexity: $$O(1)$$\n
['Math', 'JavaScript']