Dynamic Programming and Binary Search for Powerful Array Queries
Intuition\nThe problem requires finding products of elements within a certain range modulo a given number. To efficiently solve this problem, we can use dynamic
# Intuition\n**The problem requires finding products of elements within a certain range modulo a given number. To efficiently solve this problem, we can use dynamic programming to calculate the number of bits required to represent a number, perform binary search to find the maximum number within a given range, and calculate the summation of bits within the range.**\n\n# Approach\n***Dynamic Programming for Number of Bits:***\n\nUtilize dynamic programming to calculate the number of bits required to represent a number.\nStore the calculated number of bits for each number in a map to avoid redundant computations.\n\n***Binary Search for Maximum Number:***\n\nPerform a binary search to find the maximum number within a given range.\nUtilize the previously calculated number of bits to determine if a number falls within the range.\n\n***Summation of Bits:***\n\nCalculate the summation of bits within a given range.\nIterate through each bit position, calculating the contribution of ones in complete blocks and any remaining bits.\n\n***Main Function to Compute Result:***\n\nCombine the above calculations to compute the final result for a given range.\nCalculate the sum of bits within the range and adjust for any remaining bits.\n\n***Power Function and Modular Arithmetic:***\n\nCompute the result for each query using the previously defined functions.\nUtilize a power function to efficiently compute powers modulo the given number.\n\n# Complexity\n- Time complexity:\n**O(QlogN), where Q is the number of queries and N is the maximum number in the queries.**\n\n- Space complexity:\n**O(logN), due to dynamic programming and additional space for storing intermediate results.**\n\n# Code\n```\nclass Solution {\nprivate:\n    unordered_map<long long, long long> dp;\n    \n    long long power(long long n, long long expo, long long mod)\n    {\n        long long ans = 1;\n        \n        while (expo)\n        {\n            if (expo % 2)\n                ans = ans * n % mod;\n            \n            n = n * n % mod;\n            expo /= 2;\n        }\n        \n        return ans;\n    }\n    \n    long long getNumBits(long long n)\n    {\n        if (n == 0)\n            return 0;\n        \n        if (dp.count(n))\n            return dp[n];\n        \n        long long ans = 0, num = n + 1;\n        \n        for (int i = 60; i >= 0; i--)\n            if ((1LL << i) < num)\n            {\n                ans = getNumBits((1LL << i) - 1);\n                \n                long long rem = num - (1LL << i);\n                \n                ans += getNumBits(rem - 1) + rem;\n                break;\n            }\n        \n        return dp[n] = ans;\n    }\n    \n    long long getMaxNum(long long n)\n    {\n        long long left = 1, right = 1e15, ans = 0;\n        \n        while (left <= right)\n        {\n            long long mid = (left + right) / 2;\n            \n            long long placesOccupied = getNumBits(mid);\n            \n            if (placesOccupied <= n)\n                ans = mid, left = mid + 1;\n            else\n                right = mid - 1;\n        }\n        \n        return ans;\n    }\n    \n    long long getSum(long long n)\n    {\n        long long res = 0;\n        \n        for (int i = 1; i < 50; i++)\n        {\n            long long blockSize = (1LL << (i + 1));\n            long long onesInBlock = blockSize / 2;\n            \n            long long completeBlocks = n / blockSize;\n            \n            res += completeBlocks * onesInBlock * i;\n            \n            long long rem = n % blockSize;\n            res += max(0LL, rem + 1 - onesInBlock) * i;\n        }\n        \n        return res;\n    }\n    \n    long long func(long long n)\n    {\n        if (n == 0)\n            return 0;\n        \n        long long maxNum = getMaxNum(n);\n        long long placesOccupied = getNumBits(maxNum);\n        \n        long long ans = getSum(maxNum);\n        \n        maxNum++;\n        long long rem = n - placesOccupied;\n        \n        for (int i = 0; rem > 0; i++)\n            if (maxNum & (1LL << i))\n            {\n                rem--;\n                ans += i;\n            }\n        \n        return ans;\n    }\n    \n    int solve(vector<long long> &query) {\n        long long L = query[0], R = query[1], mod = query[2];\n        \n        return power(2, func(R + 1) - func(L), mod) % mod;\n    }\npublic:\n    vector<int> findProductsOfElements(vector<vector<long long>>& queries) {\n        vector<int> res;\n        \n        for (auto q: queries)\n            res.push_back(solve(q));\n        \n        return res;\n    }\n};\n\n```
['Binary Search', 'Dynamic Programming', 'C++']