1,597 views

2 Answers

0 votes
0 votes
Okay fine u can use dynamic programming here

here is the code

int arr[k+1];

for(int i=0;i<=k;i++)

arr[i]=0;

int inp[n+1];

for(int i=0;i<n;i++){

cin>>inp[i];

arr[inp[i]]++;

}

for(int i=1;i<=k;i++){

arr[i]+=arr[i-1];

}

// let q be the queries;

cin>>q;

while(q--){

int a , b;

cin>>a>>b;

cout<<arr[b]-arr[a-1]<<"\n";

}
0 votes
0 votes
Use counting sort.

We know that in counting sort we maintain the sum of the occurrences of all the elements in the array.

So array[b]-array[a-1] will return the answer in O(1) time.

Related questions

0 votes
0 votes
0 answers
1
akash.dinkar12 asked Jun 28, 2019
348 views
Suppose that we were to rewrite the for loop header in line $10$ of the COUNTINGSORT as 10 for j = 1 to A.lengthShow that the algorithm still works properly. Is the modif...
0 votes
0 votes
1 answer
2
1 votes
1 votes
1 answer
4
akash.dinkar12 asked Jun 28, 2019
655 views
Explain why the worst-case running time for bucket sort is $\Theta(n^2)$. What simple change to the algorithm preserves its linear average-case running time and makes its...