Лексикографически наименьшая перестановка массива такая, что сумма префиксов до любого индекса не равна K

Опубликовано: 22 Сентября, 2022

Дан массив arr[], состоящий из N различных положительных целых чисел и целого числа K, задача состоит в том, чтобы найти лексикографически наименьшую перестановку массива, такую, что сумма элементов любого префикса выходного массива не равна K . Если такой перестановки не существует, то выведите « -1 ». В противном случае распечатайте выходной массив.

Примеры:

Input: arr[] = {2, 6, 4, 5, 3, 1}, K = 15
Output: 1 2 3 4 6 5
Explanation:
The lexicographically smallest permutation of the given array is, {1, 2, 3, 4, 6, 5} having no prefix of sum equal to 15.

Input: arr[]={3, 1, 4, 6}, K = 12
Output: 1 3 4 6
Explanation:
The lexicographically smallest permutation of the given array is, {1, 3, 4, 6} having no prefix of sum equal to 12.

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

  • Если сумма массива равна K , то выведите « -1 », так как найти какую-либо перестановку массива, удовлетворяющую условиям, будет невозможно.
  • Отсортируйте массив в порядке возрастания.
  • Инициализируйте переменную, скажем, preSum как 0 , чтобы сохранить сумму префикса.
  • Переберите диапазон [0, N-2], используя переменную i , и выполните следующие шаги:
    • Увеличьте preSum на arr[i] .
    • Если preSum равно K, то поменять местами arr[i] и arr[i+1] , а затем разбить.
  • Наконец, после выполнения вышеуказанных шагов выведите элементы массива arr[] .

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

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

РЕКОМЕНДУЕМЫЕ СТАТЬИ