Number of smaller elements on right side

Given an array, this function will print the number of smaller elements that are on the right side of the each element

Example:

INPUT:
arr[] = {4, 10, 6, 2, 1}

OUTPUT:
smaller_elements[] = {2, 3, 2, 1, 0}

In the above example, smaller_elements[] array contains the number of smaller elements that are on thier right side of them.

Time Complexity: O()  

In this method we wil use two loops

Algorithm

1. Simply create two loops
2. In the outer loop pick all the elements ie, i =0 to n
3. In the inner loop traverse through all the elements on the right side of picked element ie, j = i+1 to n
4. If the elements on the right side of the picked element is lesser, then increment the value in ith index of smaller_elements[] array ie, arr[j] <arr[i], smaller_elements[i]++.
5. print smaller_elements[].

C++ Program

#include <bits/stdc++.h>
using namespace std;

int smallerElements(int arr[], int n)
{
	int smaller_elements[n] = {0};
	for (int i = 0; i < n; ++i) //counting the no of elements and storing in array
	{
		for (int j = i+1; j < n; ++j)
		{
			if(arr[i]>arr[j])
			{
				smaller_elements[i]++;
			}
		}
	}
	cout<<"smaller_elements[] = [";
	for (int i = 0; i < n; ++i) //printing the array
	{
		cout<<smaller_elements[i]<<" ";
	}
	cout<<"]";
}
int main()
{
	int arr[]= {4, 10, 6, 2, 1};  //creating an array
	int n = sizeof(arr)/sizeof(arr[0]); //size of the array
	smallerElements(arr, n);
	return 0;
}