Description
Solutions
Find Maximum Greatness
🤘 INTERN

Given an array arr, we can rearrange it to form another array, let's call it rearranged_arr. The greatness of the array is defined as the number of indices i, 0 ≤ i < n, where rearranged_arr[i] > arr[i]. That is, the element placed after rearrangement is greater than the initial value present at that index.

Given the initial array arr, find the maximum possible greatness which can be achieved by some rearrangement of the array.

Function Description

Complete the function findMaximumGreatness in the editor.

findMaximumGreatness has the following parameter:

  1. int arr[n]: an array of integers

Returns

int: the maximum possible greatness

Example 1: 

Input:  arr = [1, 3, 5, 2, 1, 3, 1]
Output: 4 
Explanation:

[1, 3, 5, 2, 1, 3, 1] -> original arr

[2, 5, 1, 3, 3, 1, 1] -> optimal rearranged_arr
    
Here, at indices 0, 1, 3, and 4 in bold, rearranged_arr[i] > arr[i]. It can be shown that this is the maximum possible greatness. Thus, the answer is 4.
Constraints:
    • 1 ≤ n ≤ 105
    • 1 ≤ arr[i] ≤ 109
Thumbnail 0
Testcase
Result
Case 1

input:

output: