0 like 0 dislike
1,219 views
| 1,219 views

0 like 0 dislike

Images of ques

by Expert (46,090 points)
0 like 0 dislike

## Python # Approach : Bitmasking + Prefix Multiplication

``````def findGoodArray(n):
res = []
while n :
lastSetBit = n & -n
res.append(lastSetBit)
n -= lastSetBit
return res

def getQueryResults(n,queries):
goodArr = findGoodArray(n)

prefixMul = [1]*(len(goodArr)+1)
for i in range(len(goodArr)):
prefixMul[i+1] = prefixMul[i]*goodArr[i]

res = [0]*len(queries)
for idx,[l,r,m] in enumerate(queries):
res[idx] = ( prefixMul[r]//prefixMul[l-1] ) % m
return res

print(getQueryResults(26,[[1,2,1009],[3,3,5]]))
print(getQueryResults(6,[[1,2,4],[2,2,8],[1,1,4]]))``````
by Expert (46,090 points)
0 like 0 dislike

C++ code

``````#include<bits/stdc++.h>
using namespace std;
vector<long long> goodArrays(long long int n, vector<vector<int>> &queries)
{
vector<long long> nums, ans;
int i = 0;
while (n)
{
/* extract single bit and push its corresponding decimal value because a number with exactly one set bit is power of two
for example decimal 6 = binary(110)
6 can be broken into '10'=2 and '100'=4
which sum up to 6;
since we are traversing from back of the number it will always be sorted;
*/
if (n & 1)
nums.push_back(1 << i);
n >>= 1;
i++;
}
for (auto &q : queries)
{
// if query is out of bounds
if (q[0] > nums.size() && q[1] > nums.size())
continue;
long long temp;
// if the l and r are not equal
if (q[0] != q[1])
temp = (nums[q[0] - 1] * nums[q[1] - 1]) % q[2];
else // if l==r we don't have to multiply nums[l] to nums[r];
temp = nums[q[0] - 1] % q[2];
ans.push_back(temp);
}
return ans;
}
int main()
{
long long n;
int q;
cin >> n >> q;
vector<vector<int>> queries(q, vector<int>(3));
for (int i = 0; i < q; i++)
cin >> queries[i][0] >> queries[i][1] >> queries[i][2];
vector<long long> ans = goodArrays(n, queries);
for (auto it : ans)
cout << it << " ";
return 0;
}
``````

The time complexity of the code is max(O(log(N))+O(q)), q=number of queries

by Expert (46,090 points)