Найдите числа между [L, R], которые делятся на все элементы массива
Дан массив arr[] , содержащий N положительных целых чисел, и две переменные L и R , обозначающие диапазон целых чисел от L до R (включительно). Задача состоит в том, чтобы вывести все числа от L до R , которые делятся на все элементы массива. Если такого значения не существует, выведите -1.
Input: arr[] = {3, 5, 12}, L = 90, R = 280
Output: 120 180 240
Explanation: 120, 180, 240 are the numbers which are divisible by all the arr[] elements.Input: arr[] = {4, 7, 13, 16}, L = 200, R = 600
Output: -1
Наивный подход: в этом подходе для каждого элемента в диапазоне [L, R] проверьте, делится ли он на все элементы массива.
Временная сложность: O((RL)*N)
Вспомогательное пространство: O(1)
Эффективный подход: данная проблема может быть решена с использованием базовой математики. Любой элемент, который делится на все элементы массива, кратен НОК всех элементов массива. Найдите кратные LCM в диапазоне [L, R] и сохраните в массиве. Наконец, выведите числа, хранящиеся в массиве.
Временная сложность: O(N)
Вспомогательное пространство: O(R – L)
Подход с оптимизацией пространства: для решения проблемы можно использовать следующие шаги:
- Рассчитайте НОК всех элементов заданного массива []
- Теперь проверьте LCM на эти условия:
- Если (LCM < L и LCM*2 > R) , то выведите -1.
- Если (LCM > R) , то выведите -1.
- Теперь возьмите ближайшее значение L (между L и R ), которое делится на LCM , скажем, i .
- Теперь начните печатать i и увеличивайте его на LCM каждый раз после печати, пока оно не станет больше, чем R .
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(N)
Вспомогательное пространство: О(1)