LittleMaster_7's blog

Number of elements less than VAL in an array

By LittleMaster_7, history, 8 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

»
8 years ago, # |
  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
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Thanks a lot, for your effort :)

    But actually its a sub-problem which i trying to solve. To solve that problem i need online solution.

    Any time update value and query is allowed. so preprocess will not work .

    → Reply
»
8 years ago, # |
  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
»
8 years ago, # |
← 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
  • »
    »
    8 years ago, # ^ |
      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