Создайте массив таким образом, чтобы 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.