Question

Goldman Sachs | OA | SDE -1 | 2022 | INDIA | Set-7

Answer 1

Images of ques

 

Answer 2

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]]))

Answer 3

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