# Count smaller elements on the right side of an array in C++

In this tutorial, we will learn to count smaller elements on the right side of an array in C++. We will write a function to count elements which are smaller than the current element that is on the right side.

The rightmost element will return 0.

For Example:

• Input: array= {12, 5, 2, 3, 0, 11, 3}
Output: {6, 4, 1, 1, 0, 1, 0}
• Input:array=  {5, 4, 3, 2, 1}
Output: {4, 3, 2, 1, 0}
• Input: array= {1, 2, 3, 4, 5}
Output:  {0, 0, 0, 0, 0}

Now, we will go for a simple solution. Below is the approach for the solution.

Approach:

• Firstly, initialize all the count of the array as zero.
• Now, we will use two for loops.
• Then the outer for loop will pick the elements from left to right.
• Now, the inner for loop will iterate through all the elements which are at the right of the current element.
• Then check for the condition if it is smaller or not.
• Finally, update the array.
• The time complexity of the given approach is O(n^2).
• Moreover, the auxiliary space is O(1).

You may also like:
Minimum Spanning Tree for Graph in C++

## Count smaller elements on the right side in C++

Hence, below is the implementation of this simple approach.

Code:

```#include<iostream>
using namespace std;
void constructsmaller (int *array[], int *smaller, int nh)
{
int i, j;

// initializ the counts
for (i = 0; i < nh; i++)
smaller[i] = 0;

for (i = 0; i < nh; i++)
{
for (j = i+1; j < nh; j++)
{
if (array[j] < array[i])
smaller[i]++;
}
}
}

// Utility function that will print
void printit(int array[], int seze)
{
int i;
for (i=0; i < seze; i++)
cout<< arr[i];

cout<<"\n";
}

//the main function
//use maloc function
int main()
{
int array[] = {12, 8,14, 1, 3, 30, 6, 4, 0, 2};
int nh = sizeof(array)/sizeof(array);
int *lwer = (int *)malloc(sizeof(int)*n);
constructsmaller(array, lwer, nh);
printit(lwer, nh);
return 0;
}
```

Output Explanation:

```INPUT: array={12,8,14,1,3,30,6,4,0,2}
OUTPUT: {7,6,6,1,2,4,3,2,0,0}```