LittleMaster_7's blog

Number of elements less than VAL in an array

By LittleMaster_7, history, 10 years ago, In English

Suppose, there is an array of size N. Find number of elements are less than VAL. The array may contain duplicate values.

for example,

array = [ 1 , 2 , 3 , 1 , 2 ]

VAL = 3

So answer will be = 4.

Can it done by STL. (such as set/multiset ) in logarithmic time

I already googled it ,but failed to find solution with STL.

Thanks in advance.

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
10 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

I assume some preprocessing is allowed, otherwise it is not possible. After sorting each query can be answered in using std::lower_bound.

// Preprocessing part O(n log n)
std::sort(a, a+n);
// query O(log n)
int countLess(int val)
{
    return std::lower_bound(a, a+n, val) - a;
}
→ Reply
»
10 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

If the numbers are small enough, it can also be done using a binary indexed tree.. Otherwise you can compress all numbers (queries +array) and create a bit over it

→ Reply
»
10 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Can be done in logn time using Fenwick tree or BIT. I assume that some preprocessing is allowed. As far as I know, femwick tree is not part of STL.

→ Reply
  • »
    »
    10 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    And I guess it can be done with Fenwick without preprocessing too!

    Anyway the complexity will fall to O(log(N)*log(MAX_VAL)) if used map instead of array [or some other kind of complexity with hash/unordered map :) ]

    → Reply