Найти перестановку чисел до N с определенной суммой в определенном диапазоне

Учитывая четыре числа N , L , R и S , задача состоит в том, чтобы найти перестановку первых N натуральных чисел (индексирование на основе 1), имеющую сумму как S от индекса L до R . Если перестановок несколько, то выведите любую из них. В противном случае выведите -1 .

Примеры:

Input: N = 6, L = 3, R = 5, S = 8
Output: 3 4 5 2 1 6
Explanation: The output permutation has 5 at index L and 1 at index R. The sum of the numbers from L to R is 8(5+2+1).

Input: N = 4, L = 2, R = 3, S = 2
Output: -1
Explanation: There does not exist any permutation in which the sum of numbers from index L to R is S.

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

X = R – L + 1
minSum = X(X + 1)/2
maxSum = X(2*N + 1 – X)/2

Таким образом, если данная сумма S лежит в диапазоне [minSum, maxSum] , то существует такая перестановка, что сумма всех чисел от L до R равна S . В противном случае такой перестановки не существует. Выполните следующие шаги, чтобы решить проблему:

• Определите возможную функцию (int x, int S, int N) и выполните следующие задачи:
  • Инициализируйте переменную minSum как x*(x + 1)/2 и maxSum как (x * ((2*N) – x + 1))/2 .
  • Если S меньше minSum или S больше maxSum, верните false . В противном случае вернуть true .
• Инициализируйте переменную, скажем, x как (R – L + 1) .
• Если значение, возвращаемое функцией возможного(x, S, N), возвращает false, то выведите -1 и выполните возврат из функции.
• В противном случае инициализируйте вектор v[] для хранения чисел, присутствующих в данном сегменте.
• Переберите диапазон [N, 1], используя переменную i , и выполните следующие задачи:
  • Если S – i больше, чем равно 0 , и возможная функция (x – 1, S – i, i – 1) возвращает истину , тогда установите S как (S – i) , уменьшите значение x на 1 и нажмите значение i в вектор v[].
  • Если S равно 0 , выйти из цикла.
• Если S не равно 0 , выведите -1 и вернитесь.
• Инициализируйте вектор, скажем, v1[] для хранения чисел, которых нет в данном сегменте.
• Переберите диапазон [1, N], используя переменную i , инициализируйте итератор вектора и проверьте, присутствует ли элемент i в векторе v[], используя find() или нет. Если его нет, то вставьте его в вектор v1 .
• Инициализируйте переменные j и f как 0 , чтобы напечатать результаты.
• Переберите диапазон [1, L), используя переменную i , и напечатайте значение v1[j] и увеличьте значение j на 1 .
• Переберите диапазон [L, R], используя переменную i , и напечатайте значение v[f] и увеличьте значение f на 1 .
• Переберите диапазон [R+1, N], используя переменную i , и напечатайте значение v1[j] и увеличьте значение j на 1 .

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

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