Question

Uber| Interview Experiences| SDE |Intern| Set-2

Answer 1

Problem name
K-step sequence
Problem statement
Given an array A containing N numbers that are indexed from 1 to N. You are also given Q queries

 

Each query can be described as follows:

 

L R K : Print the sum of all numbers that are available in array A, are a part of a K-step sequence, and have their indexes in the range L to R.
A K-step sequence for the given array can be defined as A(1),A(1+K),A(1+2K),... where A(i) denotes the array element at index i.

 

Example

 

Assumptions

 

N = 3
A = [1, 2, 3]
Q = 2
Queries = [[1, 2, 1], [2, 3, 2]]
Approach

 

You must determine the answer to each query:

 

For the 1st query, we have values of the array as [1, 2, 3] out of which the value [1, 2] has indexed in a given range. Therefore the answer is 3.

 

For the 2nd query, we have values of the array as [1, 3] out of which the value [3] has indexed in a given range. Therefore the answer is 3.

 

ll n,q;
ll a[maxN+5];
vector<ll> g[maxN+5],csum[maxN+5];

ll lowerBound(ll k,ll v)
{
	ll s,e,m;
	s=0;
	e=g[k].size()-1;
	while((e-s)>1)
	{
		m=s+(e-s)/2;
		if(g[k][m]<=v)
			s=m;
		else
			e=m-1;
	}
	if(g[k][e]<=v)
		return e;
	if(g[k][s]<=v)
		return s;
	return -1;
}

ll upperBound(ll k,ll v)
{
	ll s,e,m;
	s=0;
	e=g[k].size()-1;
	while((e-s)>1)
	{
		m=s+(e-s)/2;
		if(g[k][m]>=v)
			e=m;
		else
			s=m+1;
	}
	if(g[k][s]>=v)
		return s;
	if(g[k][e]>=v)
		return e;
	return -1;
}

int main()
{
    ll t,i,j,l,r,k,x,y,ans;
    scanf("%lld",&t);
    while(t--)
    {
    	scanf("%lld",&n);
    	for(i=1;i<=n;i++)
    		scanf("%lld",&a[i]);
    	for(i=0;i<=n;i++)
    	{
    		g[i].clear();
    		csum[i].clear();
    	}
    	for(i=1;i<n;i++)
    	{
    		l=0;
    		for(j=1;j<=n;j+=i)
    		{
    			g[i].push_back(j);
    			csum[i].push_back(a[j]);
    			if(l)
    				csum[i][l]+=csum[i][l-1];
    			l++;
    		}
    	}
    	scanf("%lld",&q);
    	while(q--)
    	{
    		scanf("%lld%lld%lld",&l,&r,&k);
    		if(k>=n)
    		{
    			if(l<=1)
    				printf("%lld\n",a[1]);
    			else
    				printf("0\n");
    		}
    		else
    		{
    			x=upperBound(k,l);	//first number greater than or equal to l
    			y=lowerBound(k,r);	//last number less than or equal to r
    			if(x==-1)
    				printf("0\n");
    			else if(y==-1)
    				printf("0\n");
    			else
    			{
    				ans=csum[k][y];
    				if(x)
    					ans-=csum[k][x-1];
    				printf("%lld\n",ans);
    			}
    		}
    	}
    }
    return 0;
}