Question

Goldman Sachs | OA 2022 | Summer Internship 2023 | Set - 29

Answer 1

I would categorize them as leetcode medium

 

• I would appretiate if someone post the coding soltion for the 1st question, as my only 4 testcases passed during round.

1. 

---

1. 

Answer 2

Q1.

 

public List<Integer> GOODARRAY(int N, List<List<Integer>> queries){
ArrayList<Integer> goodArray = new ArrayList<>();
oneBitCount(goodArray, N);
        
ArrayList<Integer> answer = new ArrayList<>();
long goodArrayProduct = 1;
        
  for(List<Integer> query : queries)
  {
       int l = query.get(0);
       int r = query.get(1);
       int m = query.get(2);
       for(int i=l; i<=r; i++) goodArrayProduct*=goodArray.get(i-1);
       answer.add((int)(goodArrayProduct % m));
   }   
   return answer;   
}
  public void oneBitCount(ArrayList<Integer> goodArray, int n)
  {
        int count = 0;
        while(n > 0)
        {
            if((n & 1) == 1) goodArray.add((int)Math.pow(2,count));
            count++;
            n = n>>1;
        }
   }

 

Q1.
Step 1 :- find the position of set bits in binary representation of number N and store it in a array lets call it nums;
Step 2 :- prepare prefix sum of array nums
Step 3 :- now traverse every query in queries and store your answer as ------- pow(2, prefixNums[right] - prefixNums[left - 1]) % modulo ;

 

For Q1.A similar idea has been given in the comments. I too came up with that idea and have used binary exponentiation to speed things.
For Q2. you just need to sort the array a and then do binary search / upper bound to find the index of the last match that was equal to or less than the goals scored in b's match.

 

[#include](https://leetcode.com/problems/minimum-interval-to-include-each-query) <bits/stdc++.h>
using namespace std;

int binpow(int a, int n, int mod){
	if(a == 1)return 1;
	if(n == 0)return 1;
	if(n == 1)return a%mod;
	if(n&1)return binpow(a, n/2, mod)%mod *(binpow(a, n/2, mod)%mod * a%mod)%mod;
	return binpow(a, n/2, mod)%mod * binpow(a, n/2, mod)%mod;
}

void solve(int n, vector<vector<int>>queries){
	vector<int>arr;
	int _n = n;
	int cnt = 0;
	while(_n){
		if(_n&1){
			arr.push_back(cnt);
		}
		++cnt;
		_n = _n/2;
	}
	
	vector<long long>prefix;
	prefix.push_back(0);
	
	for(int i = 1; i<=(int)arr.size();++i){
		prefix.push_back(prefix[i-1] + arr[i-1]);
	}
	for(auto&it:queries){
		int l = it[0], r = it[1], mod = it[2];
		int power = prefix[r] - prefix[l-1];
		long long ans = binpow(2, power, mod);
		cout<<ans<<"\n";
	}
	return;
}

int main() {
	int n = 26;
	vector<vector<int>>queries= {{1, 2, 1009}, {3, 3, 5}};
	solve(n, queries);
	return 0;
}

 

FOR Q2

 

[#include](https://leetcode.com/problems/minimum-interval-to-include-each-query) <bits/stdc++.h>
using namespace std;

vector<int> solve(vector<int>&a, vector<int>&b){
	sort(a.begin(), a.end());
	// number of matches with less than or equal to.
	vector<int>ans;
	int n = (int)a.size();
	for(auto&it:b){
		int idx = upper_bound(begin(a), end(a), it) - begin(a);
		if(idx == n){
			ans.push_back(n);
		}else{
			ans.push_back(idx);
		}
	}
	return ans;
}
int main() {
	vector<int>a = {1, 2, 4};
	vector<int>b = {2, 4};
	vector<int>ans = solve(a, b);
	for(auto&it:ans)cout<<it<<" ";
	cout<<"\n";
	return 0;
}