DNNJFM's blog

a counting problem
By DNNJFM, history, 8 years ago, In English

Hi, all!

I have an array a[] size of n. note that a[i] in range of 10^18. n in range of 10^6.

How to calculate cnt[] in O(n)?

Here cnt[i] = number of elements in a[] that is no greater than a[i].

For exmaple, a[] = 3 2 3 1 1 2, size n= 6

then cnt[] = 6 4 6 2 2 4.

Is there any algorithm to do that in O(n)? or in O(nlogn) if we have to sort?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

deleted

→ Reply
»
8 years ago, # |
  Vote: I like it -12 Vote: I do not like it

I am assuming the main obstacle to find the cnt[] array in O(n) would be the size of a[i], which is too large to make a count array. So,

If the constraints of a[i] were in the range of 10^6 or so, a simple count array could be created. Let the count array be c[] Then, c[i] = number of times i is present in a. After taking a prefix sum of this array, i.e. c[i] += c[i-1], c[i] would be the number of elements in a not greater than i.

After this, for(int i = 0; i < n; i++) cnt[i] = c[a[i]]; should give you the required answer in O(n)

But, since the constraints of a[i] is large, a simple count array will not work. Instead, you will have to use an unordered_map<long long,int> (details of this at http://www.cplusplus.com/reference/unordered_map/unordered_map/) to do this.

My code for this :

#include<bits/stdc++.h>
using namespace std;
unordered_map<long long,int> ha; //the map used as a count array
long long int a[1000005], cnt[100005];
int main()
{
    int n; cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i],ha[a[i]]++;
    auto j = ha.begin();
    auto i = j++;
    for(; j != ha.end(); i++,j++) (*j).second += (*i).second; //finding prefix sum of the map
    for(int i = 0; i < n; i++) cnt[i] = ha[a[i]];
    for(int i = 0; i < n; i++) cout << cnt[i] << " ";
    return 0;
}

This should be able to find the cnt[] array in O(n) time and O(n) space

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

    I think unordered_map is not sorted, so it won't work.

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

      Oops! That totally skipped my mind XD Thanks :P

      → Reply
»
8 years ago, # |
  Vote: I like it +20 Vote: I do not like it

If we have the cnt[] array, then we would be able to sort a[] in O(n). And sure we can kind of sort in linear time with counting sort, but that relies on the numbers not being too large and your numbers are pretty large.

So if you manage to calculate this cnt[] array in O(n) time, you would have a O(n) sorting algorithm for arrays of long/int. How come we haven't heard of this magnificent sorting algorithm that basically every standard library should use? Well most likely because it doesn't exist.

So I really think that O(n log n) is your best shot in this problem.

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

    So, how exactly do you sort an array in O(N) after you already have cnt counted in hashmap?

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

      Well if you look at element a[i], then you know that the position cnt[i] - 1 is a valid position for the element to end up at in the sorted array. The only tricky part is that there can be several elements of equal value, but you can solve that by keeping track of the number of times you've inserted a certain element, e.g. by using an unordered map or an additional array.

      So you just need to loop through the array and place a[i] at position cnt[i] - number_of_times_seen(a[i]) (where we count the current element as seen as well) in our sorted array.

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

        Oh, completely forgot about this, thanks.

        → Reply
»
8 years ago, # |
  Vote: I like it -10 Vote: I do not like it

BIT also works

since a[i] is 10^18, but n is just 10^6, there is alot of "unused" values, so we can compress the array like this:

if a={100,5,123456}, make it {2,1,3}

because it doest matter the value, just that it inequality remains unchanged

to do this, copy the array to another array, and sort the array then iterate the original array, use binary search to find its position in the sorted array,

then, after the array is compressed, make a BIT with size n+1, (because the possible largest value in the array is n). and iterate the original array again, assume we are now at indeks i, we do a "point update" in the BIT starting indeks a[i] with 1, we are saying that from range 0 to a[i], we add one more element. so later if we query(i), the way the BIT is set is that it will get the number of elements not greater then i

so, after we are done building the BIT, iterate the array once more, if we are in indeks i, we query a[i] in the bit, and that value is what cnt[i] is...

total complexity: sorting (n log n), n point updates in bit (n log n), so total complexity is O(n log n)

my code: https://ideone.com/Uhkm60

maybe there are simpler approaches, but just sharing mine

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Or you could solve it without using BIT, so it works faster and it is easier to understand.

    Spoiler
    → Reply