Минимизируйте замены самого большого левого элемента массива, необходимого для того, чтобы сделать все элементы массива равными

Дан массив arr[] , состоящий из N целых чисел, задача состоит в том, чтобы сделать все элементы массива равными, заменив крайний левый самый большой элемент массива самым большим элементом, строго меньшим, чем текущее максимальное минимальное количество раз.

Примеры:

Input: arr[] = { 1, 1, 2, 2, 3<}
Output: 4
Explanation: Following operations reduces the required number of operations to minimum:

1. Leftmost largest array element is arr[4]( = 3). Replacing it with the largest element smaller than the current largest, arr[3] (= 2), the array modifies to {1, 1, 2, 2, 2}.
2. Leftmost largest element of the array is arr[2]( = 2). Replacing it with the largest element smaller than the current largest, arr[1] (= 1), the array modifies to {1, 1, 1, 2, 2}.
3. Leftmost largest element of the array is arr[3]( = 2), replacing it with the largest element smaller than the current largest, arr[1] (= 1), the array modifies to {1, 1, 1, 1, 2}.
4. Leftmost largest element of the array is arr[4]( = 2). Replacing it with the largest element smaller than the current largest, arr[1] (=1), the array modifies to {1, 1, 1, 1, 1}

Therefore, a minimum of 4 moves are needed.

Input: arr[] = {5, 1, 3} 
Output: 3

Подход: проблема может быть решена путем сортировки массива в порядке убывания на основе наблюдений, что на каждом шаге элемент массива заменяет все элементы, которые больше, чем текущий элемент массива. Следуйте инструкциям, чтобы решить проблему:

• Отсортируйте массив в порядке убывания.
• Инициализируйте переменную, скажем, count как 0 , чтобы подсчитать общее количество необходимых ходов.
• Переберите диапазон [1, N – 1] , используя переменную i , и выполните следующие шаги:
  • Если arr[i] != arr[i – 1] , тогда счетчик увеличивается на i .
• Наконец, после выполнения вышеуказанных шагов полученное значение печати считается ответом .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N * log(N))
Вспомогательное пространство: O(1)