Создайте массив таким образом, чтобы GCD каждого элемента с их индексами был уникальным

Имея два целых числа L и R , постройте массив заданного размера N таким образом, чтобы НОД (наибольший общий делитель) элемента с их индексами (индексация на основе 1) был уникальным для каждого индекса. Задача состоит в том, чтобы напечатать массив или вывести -1, если это невозможно.

Примеры:

Input: N = 10, L = 1, R = 15
Output: 1 2 3 4 5 6 7 8 9 10
Explanation: GCD(Arr[i], i) at every index starting from 1 till N is {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} are all distinct.

Input: N = 5, L = 11, R = 100
Output: 11 12 12 12 15 

Подход: Для решения задачи используйте следующую идею:

GCD of any number with their indices at max can be the indices itself so we need to find any multiple in the range L to R for the given number to have distinct set of GCD’s for the whole array

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

• Инициализируйте массив размером N и создайте переменную pos, изначально истинную , чтобы сохранить, существует ли ответ.
• Перебрать массив для всех индексов от 1 до N (индексирование на основе 1) .
• Найдите первое число больше L , которое делится на текущий индекс.
  • если число больше, чем R , обновить pos до false и завершить цикл.
  • иначе сохраните число в массиве и продолжите итерацию.
• Распечатайте массив как конечный результат.

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

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