## Introduction

This blog will discuss the solution to the problem of counting smaller elements on the right side.

### Problem Statement

We are given an unsorted array arr[] which consists of distinct integers, and the size of the array is N. Our task is to construct another array countSmaller[] where countSmaller[i] will represent the count of elements that are less than the arr[i] and are present on the right side of the array.

### Sample Examples

**Example 1:**

```
Input:
N=3, arr[] = {3, 2, 1}
Output:
{2, 1, 0}
Explanation:
For arr[0], two elements on the right side are smaller.
For arr[1], one element on the right side is smaller.
For arr[2], 0 elements on the right side are smaller.
```

**Example 2:**

```
Input:
N=5, arr[] = {7, 1, 5, 2, 10}
Output:
{3, 0, 0, 2, 0}
Explanation:
For arr[0], three elements on the right side are smaller.
For arr[1], 0 elements on the right side is smaller.
For arr[2], 0 elements on the right side are smaller.
For arr[3], 2 elements on the right side are smaller.
For arr[4], 0 elements on the right side are smaller.
```

## Brute Force Approach

- The brute force approach for this problem is to make an array named countSmaller[] where we will store the smaller elements on the right side for every element of the array.
- We will use nested for loops to count the number of smaller elements on the right side for every element.
- We will increment the count whenever we see any element present on the right side of the current element, and when the loop ends, we will assign countSmaller[i], The value of this count.
- After both the loops are over, we will print the countSmaller array.

### Implementation in C++

```
// C++ code for counting smaller elements on the right side
#include <iostream>
using namespace std;
// function to count smaller elements on the right side of the array
void countSmallerElementsOnRightSide(int arr[], int n)
{
// to store the count for every element
int countSmaller[n] = {};
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
// if condition is true then we will increment the
// corresponding index value in the countSmaller arrray
if (arr[i] > arr[j])
{
countSmaller[i]++;
}
}
}
for (int i = 0; i < n; i++)
{
cout << countSmaller[i] << " ";
}
cout << endl;
}
// Driver code
int main()
{
int arr[] = {19, 1, 5, 20, 21, 7, 9, 4, 10, 30};
int n = 10;
countSmallerElementsOnRightSide(arr, n);
return 0;
}
```

**Output:**

```
Input: arr[] = {19, 1, 5, 20, 21, 7, 9, 4, 10, 30}
Output: 6 0 1 4 4 1 1 0 0 0
```

#### Complexity Analysis

**Time Complexity: **O(N²)

Since we are using two nested for loop in this approach, therefore the time complexity will be O(N²)

**Space Complexity: **O(1)