Минимальное количество ходов, необходимое для сортировки массива путем замены на X

Дан целочисленный массив, arr[] размера N и целое число X . Задача состоит в том, чтобы отсортировать массив в порядке возрастания за минимальное количество ходов, заменяя местами любой элемент массива больше X на X любое количество раз. Если это невозможно, выведите -1 .

Примеры:

Input: arr[] = {1, 3, 4, 6, 5}, X = 2
Output: 3
Explanation: Swap arr[1] = 3 with X = 2, arr[] becomes {1, 2, 4, 6, 5} and X = 3.
Swap arr[2] = 4 with X = 3, arr[] becomes {1, 2, 3, 6, 5} and X = 4.
Swap arr[3] = 6 with X = 4, arr[] becomes {1, 2, 3, 4, 5}.

Input: arr[] = {7, 5}, X = 6 
Output: -1
Explanation: It is not possible to sort the array using the given conditions.

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

• Инициализируйте переменную как 0, чтобы сохранить требуемый результат.
• Пройдите массив, arr[] в диапазоне [0, N-1], используя переменную i
  • Если значение arr[i]>arr[i+1] , выполните итерацию в диапазоне [0, i] с использованием переменной j и замените arr[j] на X , если значение arr[j]>X , а увеличивая значение ans на 1.
• Проверьте, отсортирован ли массив. Если нет, то обновите ans до -1.
• Выведите значение ans в качестве результата.

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

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