Number of smaller elements on right side

0
270
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;
}

Try It

 

LEAVE A REPLY

Please enter your comment!
Please enter your name here