Wednesday, 27 Oct 2021

# Count smaller elements present in the array for each array element

Given an array arr[] consisting of N integers, the task is for each array element, say arr[i], is to find the number of array elements that are smaller than arr[i].
Examples:

Input: arr[] = {3, 4, 1, 1, 2}Output: 3 4 0 0 2Explanation:The elements which are smaller than arr(= 3) are {1, 1, 2}. Hence, the count is 3.The elements which are smaller than arr(= 4) are {1, 1, 2, 3}. Hence, the count is 4.The elements arr(= 1) and arr(= 1) are the smallest possible. Hence, the count is 0.The elements which are smaller than arr(= 2) are {1, 1}. Hence, the count is 2.
Input: arr[] = {1, 2, 3, 4}Output: 0 1 2 3

Naive Approach: The simplest approach is to traverse the array and for each array element, count the number of array elements that are smaller than them and print the counts obtained.Below is the implementation of the above approach:

C++

#include
using namespace std;

void smallerNumbers(int arr[], int N)
{

for (int i = 0; i < N; i++) {                     int count = 0;                     for (int j = 0; j < N; j++) {                             if (arr[j] < arr[i]) {                 count++;             }         }                              cout