Divide and conquer

Question

Reply with solution @Arjun sir,@habibkhan,@vijaycs

Comments

using HASHING data-structure we can do it in O(n) ...

---

i got it

---

can be solved using counting sort. (Only partial logic of counting sort needed)

Answer 1

One possible way.

1. Construct a count array such that count[m] =  No of elements with value m // O(n)
2. Convert count to a cumulative count array such that count[m] = No of elements upto and including m // O(k)
3. Range Query[a,b] = count[b] - count[a-1]  //assuming $b >= a$
4. Total preprocessing Time = O(n+k)

code 

Comments

cannot see code