Home » Interview » Array Interview Questions » Number of smaller elements on right side

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

 

vote
Article Rating
READ  Find the Only Repetitive Element Between 1 to N-1
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x