2 Solutions | Simulation, Bit Mask + Binary Search
Solution-1: Simualtion (TLE -- Passes 98.41% TCs)\n1. STEP-1: Identify max number from queries -- O(500)\n2. STEP-2: generate bigNums array for intergers 1 to m
# Solution-1: Simualtion (TLE -- Passes 98.41% TCs)\n1. **STEP-1:** Identify max number from queries -- O(500)\n2. **STEP-2:** generate bigNums array for intergers 1 to maxNo. -- O(N) \n3. **STEP-3:** Iterate over each quey and generate result -- O(q * N)\n4. **STAT:** TLE -- 746 / 758 test cases passed -- 98.41%\n# Solution-2: Binary Search + Bit Mask\n\n# Code (Solution-1):\n```\n#define ll long long\n#define ull unsigned long long\nclass Solution {\npublic:\n    // SOL-1: SIMULATION -- TC: O(Q*N), SC: O(N) -- TLE -- 746 / 758 test cases passed -- 98.41%\n    vector<int> findProductsOfElements(vector<vector<long long>>& queries) \n    {\n        // STEP-1) Identify max number from queries -- O(500)\n        ll maxNo = getMaxFromQueries(queries);\n        \n        // STEP-2) generate bigNums array for intergers 1 to maxNo. -- O(N) \n        vector<ll> bigNums = generateBigNums(maxNo);\n\n        // STEP-3) Iterate over each quey and generate result -- O(q * N)\n        vector<int> ans;\n        for ( auto query : queries )\n        {\n            ll start = query[0], end = query[1], mod = query[2];\n            ull prod = 1;\n            for ( ll i=start; i<=end; i++) {\n                prod *= bigNums[i];\n            }\n            ans.push_back(prod%mod);\n        }\n        return ans;\n    }\n    \n    ll getMaxFromQueries(vector<vector<ll>>& queries)\n    {\n        ll ans = 0;\n        for ( auto query : queries ) {\n            ans = max(ans, query[1]);\n        }\n        return ans;\n    }\n    \n    vector<ll> generateBigNums(ll maxNo)\n    {\n        vector<ll> bigNums;\n        for ( ll i=1; i<=maxNo+1; i++ )\n        {\n            bitset<25> a(i);\n            string s = a.to_string();\n            //cout << s << " ";\n            reverse(s.begin(), s.end());\n            for ( int i=0; i<s.size(); i++ )\n            {\n                if ( s[i] == \'1\' )\n                    bigNums.push_back(pow(2,i));\n            }\n        }\n        return bigNums;\n    }\n};\n```\n# Code (Solution-2):\n```\nusing LL = long long;\n\nclass Solution {\npublic:\n    vector<int> findProductsOfElements(vector<vector<LL>>& queries) {\n        vector<int> result;\n        result.reserve(queries.size());\n        for (const auto& query : queries) {\n            LL prefix_sum_1 = prefixSumTillIndex(query[0]);\n            LL prefix_sum_2 = prefixSumTillIndex(query[1] + 1);\n\n            result.push_back(pow(2, prefix_sum_2 - prefix_sum_1, query[2]));\n        }\n\n        return result;\n    }\n\nprivate:\n    // Count the bits for all numbers from 1 to `value - 1`.\n    // Return the bit value sum and total count.\n    pair<LL, LL> sumAndCountBitsBeforeValue(LL value) {\n        LL bit_sum = 0;\n        LL bit_count = 0;\n        for (LL bit = 0, power = 1; power < value; bit++, power <<= 1) {\n            LL cur = (value >> (bit + 1)) << bit;\n            cur += max(0LL, (value % (power << 1)) - power);\n            bit_count += cur;\n            bit_sum += bit * cur;\n        }\n        return {bit_sum, bit_count};\n    }\n\n    LL getValueFromIndex(LL index) {\n        index++;\n        LL low = 1, high = 1LL << 50;\n\n        while (low < high) {\n            LL mid = low + (high - low) / 2;\n            if (sumAndCountBitsBeforeValue(mid + 1).second < index) {\n                low = mid + 1;\n            } else {\n                high = mid;\n            }\n        }\n        return low;\n    }\n\n    LL prefixSumTillIndex(LL index) {\n        LL value = getValueFromIndex(index);\n        auto [bit_sum, bit_count] = sumAndCountBitsBeforeValue(value);\n        // Also include the last value\'s partial bits.\n        if (bit_count < index) {\n            for (int bit = 0; bit_count < index; bit++, value >>= 1) {\n                bit_sum += bit * (value % 2);\n                bit_count += value % 2;\n            }\n        }\n        return bit_sum;\n    }\n\n    // Calculate `(x ^ y) % mod` by converting the y into binary bits.\n    int pow(LL x, LL y, int mod) {\n        if (y <= 0) {\n            return 1 % mod;\n        }\n        x %= mod;\n        LL result = 1;\n        while (y) {\n            if (y & 1) {\n                result = multiply(result, x, mod);\n            }\n            x = multiply(x, x, mod);\n            y >>= 1;\n        }\n        return result;\n    }\n\n    int multiply(LL x, LL y, int mod) {\n        return ((x % mod) * (y % mod)) % mod;\n    }\n};\n```
['C', 'Simulation', 'Binary Tree', 'Bitmask']