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
- Simply create two loops
- In the outer loop pick all the elements ie, i =0 to n
- In the inner loop traverse through all the elements on the right side of picked element ie, j = i+1 to n
- 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]++.
- 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; }