Give a high-level pseudocode for an algorithm that, given a list of n integers f

Question

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 0(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

Explanation / Answer

Step 1: Create an array A of size k.Initailize all the elemnents 0

Step 2: Input all the elements between 0 to k-1 and start processing it
as follows:
for every element e,
increase the count A[e].
eg: If an element is 2, then value in A[2] should be increased by 1.

Step 3:
for element a & b :
Output the array between A[a] & A[b].
i.e
   if(a<k && b<k)
       Output the array between A[a] & A[b].
   else
   if(a<k && b>k)
       Output the array between A[a] & A[k-1].  
   else
   output no elemnt is present in the given range

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.