FastPrep
Problem · Array

Find Maximum Greatness

Learn this problem
● EasyTwilioINTERNOA

Problem statement

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

findMaximumGreatness(arr: int[]) → int

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

Examples

Example 1

arr = [1, 3, 5, 2, 1, 3, 1]return = 4
[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

More Twilio problems

drafts saved locally
public int findMaximumGreatness(int[] arr) {
    // write your code here
}
arr[1, 3, 5, 2, 1, 3, 1]
expected4
checking account