Give a highlevel pseudocode for an algorithm that given a li

Give a high-level pseudocode for an algorithm that, given a list of n integers from the set {0, 1, . . . , k 1}, preprocesses its input to extract and store information that makes it possible to answer any query asking how many of the n integers fall in the range [a..b] (with a and b being input parameters to the query) in O(1) time. Explain how your algorithm works.

The preprocessing time should be O(n + k) in the worst case. Provide an argument showing that your preprocessing algorithm meets that bound.

Solution

Ans: pseudocode for an algorithm

function countingSort(array, min, max)

count: array of (max – min + 1) elements

initialize count with Zero

for every number in array do

    count[number – min] := count[number-min] + 1

done

z:= 0

    while(count[ i – min] >0) do // for I from min to max

      array[z] := i

      z := z + 1

      count[i – min] := count [i – min] – 1

    done

   done

Find Pseudo Code

find(a, b)