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

Question

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.

Answer 1

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

}

Answer 2

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.