Optimal Approach in Swift 🚦 Find Products of elements of Big Array
\n## Intuition\nThe problem involves calculating the product of numbers within a given range where the numbers are represented by their binary powers of 2. Each
\n## Intuition\nThe problem involves calculating the product of numbers within a given range where the numbers are represented by their binary powers of 2. Each power of 2 follows a specific pattern. To solve the problem efficiently, we can utilize these patterns to determine the counts of each power of 2 in the given range and then calculate the resulting product modulo a given value.\n\n## Approach\n1. **Process Each Query:**\n   - For each query, get the start (`s`) and end (`t`) indices and the modulo value (`mod`).\n   - Adjust the end index by adding 1 because the range is inclusive.\n\n2. **Binary Search for Upper Bound:**\n   - Use binary search to find the highest number `n1` where the sum of the count of powers of 2 in integers from 0 to `n1-1` is less than or equal to `s`.\n   - Repeat the process for `t` to find `n2`.\n\n3. **Get Counts of Powers of 2:**\n   - Calculate the counts of each power of 2 for numbers up to `n1` and `n2`.\n   - Adjust these counts to match exactly `s` and `t` by incrementing the counts until they sum up to the desired target.\n\n4. **Compute Range Counts:**\n   - Subtract the counts obtained for `s` from the counts obtained for `t` to get the counts for the range `[s, t)`.\n\n5. **Calculate Product:**\n   - Use these counts to calculate the product of powers of 2 modulo `mod`.\n   - For each power of 2, compute its contribution and handle the rollovers to the next higher power.\n\n6. **Final Adjustment for Highest Power:**\n   - For the highest power of 2, continue reducing the count by doubling the base and updating the product.\n\n## Complexity\n- **Time complexity:** \n  - Binary search in the given range [1, 100000000000000] will take $$O(\\log(\\text{MAX}))$$ iterations.\n  - Calculating the sum of frequencies for each power of 2 will take $$O(\\log(\\text{MAX}))$$ time.\n  - Adjusting the counts and calculating the product will take $$O(\\log(\\text{MAX})$$ time.\n  - For $$Q$$ queries, the total time complexity is $$O(Q \\cdot \\log^2(\\text{MAX}))$$.\n\n- **Space complexity:**\n  - The space used for storing counts of powers of 2 is $$O(\\log(\\text{MAX}))$$.\n  - The space complexity is $$O(\\log(\\text{MAX}))$$.\n\n![Screenshot 2024-05-17 at 22.24.19.png](https://assets.leetcode.com/users/images/17afed9f-63ca-481d-a2fc-43eb73e5c86e_1715992318.1230972.png)\n\n\n```swift []\nclass Solution {\n    // Function to find products of elements for each query\n    func findProductsOfElements(_ queries: [[Int]]) -> [Int] {\n        var response = [Int](repeating: 0, count: queries.count)\n        \n        // Process each query individually\n        for (i, query) in queries.enumerated() {\n            let s = Int64(query[0]) // Start index\n            let t = Int64(query[1]) + 1 // End index\n            let mod = Int64(query[2]) // Modulo value\n            response[i] = solve(s, t, mod) // Solve for the current query\n        }\n        \n        return response\n    }\n    \n    // Function to solve a single query\n    private func solve(_ s: Int64, _ t: Int64, _ mod: Int64) -> Int {\n        // Get the highest number x such that the sum of count of \n        // powers of 2 in integers in the range [0, x-1] is <= s\n        let n1: Int64 = s > 0 ? getNextHigher(1, 100000_00000_00000, s) : 0\n        var c1: [Int64] = s > 0 ? getLowerCounts(n1) : Array(repeating: 0, count: 51)\n        adjust(&c1, n1, s) // Adjust counts for s\n        \n        // Get the highest number x such that the sum of count of \n        // powers of 2 in integers in the range [0, x-1] is <= t\n        let n2: Int64 = getNextHigher(1, 100000_00000_00000, t)\n        var c2: [Int64] = getLowerCounts(n2)\n        adjust(&c2, n2, t) // Adjust counts for t\n        \n        // Calculate counts of each power of 2 in the desired range [s, t)\n        for i in 0..<50 {\n            c2[i] -= c1[i]\n        }\n        \n        // Calculate powers of 2 modulo mod\n        var pow = [Int64](repeating: 1, count: 50)\n        for i in 1..<50 {\n            pow[i] = (pow[i - 1] << 1) % mod\n        }\n        \n        // Calculate the product of powers of 2\n        var product: Int64 = 1\n        var next: Int64 = 2\n        c2[50] = 0\n        \n        // Iterate through each power of 2\n        for i in 1..<50 {\n            // Calculate remainder and division\n            let remainder = Int((c2[i] * Int64(i)) % (Int64(i) + 1))\n            let division = (c2[i] * Int64(i)) / (Int64(i) + 1)\n            // Update product\n            product = (product * pow[remainder]) % mod\n            \n            // Roll over the division to the next higher power of 2\n            c2[i + 1] += division\n            next <<= 1\n        }\n        \n        // Calculate product for the highest power of 2\n        var base = next % mod\n        while c2[50] > 0 {\n            if c2[50] % 2 == 1 {\n                product = (product * base) % mod\n            }\n            base = (base * base) % mod\n            c2[50] >>= 1\n        }\n        \n        return Int(product % mod)\n    }\n    \n    // Function to adjust counts\n    private func adjust(_ counts: inout [Int64], _ x: Int64, _ target: Int64) {\n        var index = 0\n        var x = x\n        // Increment counts until it matches target\n        while counts[50] != target {\n            if x == 0 {\n                print("Error")\n                break\n            }\n            if x % 2 != 0 {\n                counts[index] += 1\n                counts[50] += 1\n            }\n            x >>= 1\n            index += 1\n        }\n    }\n    \n    // Function to get the next higher number for which the sum of count of \n    // powers of 2 is <= target\n    private func getNextHigher(_ from: Int64, _ to: Int64, _ target: Int64) -> Int64 {\n        if from == to {\n            return from\n        }\n        let mid = from + (to + 1 - from) / 2\n        let counts = getLowerCounts(mid)\n        if counts[50] > target {\n            return getNextHigher(from, mid - 1, target)\n        } else {\n            return getNextHigher(mid, to, target)\n        }\n    }\n    \n    // Function to get counts of each power of 2 less than x\n    private func getLowerCounts(_ x: Int64) -> [Int64] {\n        var counts = [Int64](repeating: 0, count: 51)\n        var total: Int64 = 0\n        var i = 0\n        var next: Int64 = 1\n        // Calculate counts for each power of 2\n        while next < x {\n            counts[i] = (x / (2 * next)) * next + max((x % (2 * next)) - next, 0)\n            total += counts[i]\n            i += 1\n            next <<= 1\n        }\n        // Store total count at the end of the array\n        counts[50] = total\n        return counts\n    }\n}\n```
['Array', 'Binary Search', 'Swift']