From brute force GCD to factors, counting, and binary search
Intuition\n Describe your first thoughts on how to solve this problem. \n\nThe most basic solution below works for most cases, but you can try to memoize or inl
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\nThe most basic solution below works for most cases, but you can try to memoize or inline your `gcd` function and will still result in TLE.\n\n```\nimport Algorithms\n\nclass Solution {\n    func gcdValues(_ nums: [Int], _ queries: [Int]) -> [Int] {\n        \n        var p: [Int] = []\n\n        // n * (n - 1) / 2 pairs\n        for n in nums.combinations(ofCount: 2) {\n            // gcd() not provided, copy from swift-numerics\n            p.append(gcd(n[0], n[1]))\n        }\n\n        p.sort()\n\n        return queries.map {\n            p[$0]\n        }\n    }\n}\n```\n\nThe runtime and space is at least `O(n^2)` so we need to reduce this in order to have a valid solution for large `n`.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\nReference solutions: [Puneet7373](https://leetcode.com/problems/sorted-gcd-pair-queries/solutions/5875685/c-divisors-counting-and-binary-search-o-n-sqrt-maxelement-easy-to-understand), [poiuyt123](https://leetcode.com/problems/sorted-gcd-pair-queries/solutions/5876586/comments-and-dry-run)\n\nInstead of calculating the `gcd` of each pair, we can calculate the number of elements that have `i` as a factor, up to the maximum of `nums` as the `gcd` of a pair of numbers cannot be more than the maximum of all of `nums`.\n\nIn the range of `1 ... squareRoot(nums[i])`, we determine if `i` or `nums[i] / i` divides `nums[i]` and keep the count of number of elements that have those values as factors.\n\nGoing from the maximum in `nums` to `0`, we count how many elements have `i` as a factor. The number of pairs is the combination `count[i] C 2` to remove `(j, i)` (per problem description).\n\nHowever, not all of these pairs may have a `gcd = i` but may have a `gcd = x * i` (multiple of `i`). Subtract out the factors that are multiples of `i` starting at `2 * i`. This is why we iterate down from the maximum to `0`.\n\nFor example, if `i = 2` and `nums = [6, 12]`, then `factorCount[2] == 2`, but that is not the correct `gcd` for that pair (`6`). We must remove the number of elements that have a multiple of `2` as a factor, where eventually we will subtract `count[i * 3 = 6] = 2` from the `gcd` count.\n\nAt this point, we have already reduced our runtime to somewhere around `O(n * sqrt(m) + m)` where `n = nums.count` and `m = nums.max()`. Per problem constraints, this will be less than `O(n^2)`.\n\nFor queries, we compute the prefix sum of 0-based ranks which allows us to perform binary search on the count-space.\n\nOverall runtime is somewhere around: `O(n * sqrt(m) + m + q * log(m))`. Might be missing an `n` somewhere.\n\n# Code\n\nVariable names differ from explanation but applies same logic.\n\n```swift []\nclass Solution {\n    func gcdValues(_ nums: [Int], _ queries: [Int]) -> [Int] {\n        \n        // d[i] == # of elements that have\n        // factor of i\n        let m = nums.max()!\n        var d = Array(repeating: 0, count: m + 1)\n\n        for i in 0 ..< nums.count {\n            let c = nums[i]\n\n            // get all factors of c\n            for j in 1 ... Int(Double(c).squareRoot()) {\n                // j divides c\n                if c % j == 0 {\n                    d[j] += 1\n\n                    // c / j divides c\n                    // example: c = 12, j = 4, c / j = 3\n                    if j != c / j {\n                        d[c / j] += 1\n                    }\n                }\n            }\n        }\n\n        // gcdCount[i] == # of elements who have gcd of i\n        var gcdCount = Array(repeating: 0, count: m + 1)\n\n        for i in stride(from: m, to: 0, by: -1) {\n\n            // # of pairs with factor == i = (c * (c - 1)) / 2\n            // (combination)\n            let c = d[i]\n            gcdCount[i] = (c * (c - 1)) / 2\n\n            // remove pairs who have factors as a multiple of i,\n            // so they actually have a gcd > i\n            var j = 2 * i\n\n            while j <= m {\n                gcdCount[i] -= gcdCount[j]\n                j += i\n            }\n        }\n\n        // build prefix sum for ranks and use\n        // binary search for queries\n        var preSum = Array(repeating: 0, count: m + 1)\n        preSum[0] = gcdCount[0]\n\n        for i in 1 ... m {\n            preSum[i] = preSum[i - 1] + gcdCount[i]\n        }\n\n        var t: [Int] = []\n\n        for q in queries {\n            var l = 1\n            var r = m\n            var c = 0\n\n            while l <= r {\n                let m = l + (r - l) / 2\n\n                if preSum[m] > q {\n                    c = m\n                    r = m - 1\n                } else {\n                    l = m + 1\n                }\n            }\n\n            t.append(c)\n        }\n\n        return t\n    }\n}\n```
['Hash Table', 'Binary Search', 'Swift', 'Combinatorics', 'Counting']