Создайте массив N-размера с равной разницей соседних элементов, содержащих заданные числа A и B

Учитывая два натуральных числа A и B (B >= A) и целое число N , ваша задача состоит в том, чтобы сгенерировать массив натуральных чисел в неубывающем порядке, так что и A, и B должны быть частью массива, и разница между каждая пара соседних элементов одинакова, сохраняя максимальный элемент массива как можно меньшим.

Пример:

Input: A = 10, B = 20, N = 4
Output: 5 10 15 20
Explanation: The array {5, 10, 15, 20} contains only natural numbers and both A=10 and B=20 are included in the array. The difference between every adjacent pair is 5 and the maximum element is 20 which can’t be further reduced.

Input: A = 12, B = 33, N = 2
Output: 12 33

Input: A = 7, B = 17, N = 5
Output: 2 7 12 17 22

Подход: Требуемый массив образует серию AP. Поскольку A и B должны быть включены в AP, общая разность d между соседними терминами должна быть делителем (B – A). Для минимизации наибольшего члена оптимальным подходом является создание массива с наименьшей возможной общей разностью, удовлетворяющей заданным условиям. Проблема может быть решена, выполнив следующие шаги:

• Перебрать все значения d от 1 до BA .
• Если d — множитель BA и количество элементов от A до B с общей разностью d не больше N , то идем дальше. В противном случае перейдите к следующему значению d .
• Возможны два случая
  • Случай 1. Количество элементов, меньших или равных B , имеющих общую разность d больше, чем N. В этом случае первым элементом массива будет B – (d*(N-1)) .
  • Случай 2 – Количество элементов, меньших или равных B , имеющих общую разность d , меньше, чем N. В этом случае первым элементом массива будет B – d*( B-1 )/d (т.е. 1).
• Распечатайте массив, используя первый элемент и общую разность.

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

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