# Cormen Edition 3 Exercise 8.2 Question 4 (Page No. 197)

179 views
Describe an algorithm that, given $n$ integers in the range $0$ to $k$ preprocesses its input and then answers any query about how many of the $n$ integers fall into the range $[a..b]$ in $O(1)$ time.Your algorithm should use $\Theta(n+k)$ preprocessing time.

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";

}
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

1
113 views
Suppose that we were to rewrite the for loop header in line $10$ of the COUNTINGSORT as 10 for j = 1 to A.length Show that the algorithm still works properly. Is the modified algorithm stable?
COUNTING-SORT(A, B, k) 1 let C[0, ,k] be a new array 2 for i = 0 to k 3 C[i] = 0 4 for j = 1 to A.length 5 C[A[j]] = C[A[j]] + 1 6 // C[i] now contains the number of elements equal to i . 7 for i =1 to k 8 C[i] = C[i] + C[i-1] 9 // C[i] now contains the ... [C[A[j]]] = A[j] 12 C[A[j]] = C[A[j]] - 1 illustrate the operation of COUNTING-SORT on the array $A=\langle 6,0,2,0,1,3,4,6,1,3,2 \rangle$
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 worst-case running time $O(n\ lg\ n)$?