# 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[0]); 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}

## Leave a Reply