Given an array a[], create another array ar_low[] such that ar_low[i] = number of elements less than or equal to ar[i] in ar[i+1:n-1]

#include <stdio.h>
#include <map>

/* Map to hold an element and its count of number of elements <= */
/* Element is the key and Count of <= is the Value */
typedef std::map<int, int> Map;


/* Inserts the element into map */
/* Returns count of <= */
int insert(Map &m, int el)
{
/* Find the element >= el */
Map::iterator mit = m.lower_bound(el);

/* If el already exists, increment its Count of <= */
if(mit != m.end() && (mit->first == el ))
{
return ++mit->second;
}

Map::iterator mit1 = mit;

/* Increment the count of the greater elements by 1 */
for(; mit != m.end(); ++mit)
{
mit->second++;
}

/* Find prev element, set current element count as prev element count + 1 */
if(mit1 != m.begin())
{
--mit1;
return m[el] = mit1->second + 1;
}

return m[el] = 0;
}

void findCount(int a[], int a_low[], int n)
{
Map m;

/* Start from the end */
while(n--)
{
a_low[n] = insert(m, a[n]);
}
}

int main()
{
int n;

scanf("%d", &n);

int a[n], a_low[n];

int i;

for(i = 0; i < n; ++i)
scanf("%d", a + i);

findCount(a, a_low, n);

for(i = 0; i < n; ++i)
printf("%d ", a_low[i]);

printf("\n");

}
Advertisements

One thought on “Given an array a[], create another array ar_low[] such that ar_low[i] = number of elements less than or equal to ar[i] in ar[i+1:n-1]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s