FastPrepFastPrep
Problem Brief

Find Maximum Greatness

INTERNOA

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

1Example 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

Limits and guarantees your solution can rely on.

  • 1 ≤ n ≤ 105
  • 1 ≤ arr[i] ≤ 109
public int findMaximumGreatness(int[] arr) {
    // write your code here
}
Input

arr

[1, 3, 5, 2, 1, 3, 1]

Output

4

Sign in to submit your solution.