Найдите массив, который при сортировке образует AP и имеет минимальный максимум

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

Даны три положительных целых числа N , X и Y(X<Y) . Задача состоит в том, чтобы найти массив длины N , содержащий как X , так и Y , и при сортировке по возрастанию массив должен образовывать арифметическую прогрессию

Примеры:

Input: N = 5, X = 20, Y = 50
Output: 20 30 40 50 10 
Explanation: The array when sorted in increasing order forms an arithmetic progression with common difference 10.

Input: N = 17, X = 23445, Y = 1000000
Output: 23445 218756 414067 609378 804689 1000000 1195311 1390622 1585933 1781244 1976555 2171866 2367177 2562488 2757799 2953110 3148421 
Explanation: The array when sorted in increasing order forms an arithmetic progression with common difference 195311.

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

Выполните следующие шаги, чтобы решить данную проблему:

  • Проверьте, присутствуют ли какие-либо элементы, имеющие общее различие между X и Y . Для этого проверьте, делится ли ( YX ) на ( N -1). Если оно делится, то уменьшите N , и общая разность d будет равна:

d = (Y-X)/(N-1)

  • Если оно не делится, то уменьшите (n-1) и повторите описанный выше шаг в цикле, пока знаменатель не станет ненулевым.
  • Если таких элементов между X и Y не существует, то общая разность d определяется как:

d = (Y-X)

  • Пусть результирующий массив будет сохранен в векторе ans . Вставьте найденные элементы между X и Y в вектор и используйте цикл for.
  • Если N не равно нулю, вставьте элементы в ans , начиная с ( Xd ) с общей разностью d .
  • Если N равно нулю, выведите an . В противном случае вставляйте элементы в ans , начиная с ( Y+d ), пока не будет получен требуемый массив.

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

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

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