Найдите числа между [L, R], которые делятся на все элементы массива

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

Дан массив 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)

Подход с оптимизацией пространства: для решения проблемы можно использовать следующие шаги:

  1. Рассчитайте НОК всех элементов заданного массива []
  2. Теперь проверьте LCM на эти условия:
    1. Если (LCM < L и LCM*2 > R) , то выведите -1.
    2. Если (LCM > R) , то выведите -1.
  3. Теперь возьмите ближайшее значение L (между L и R ), которое делится на LCM , скажем, i .
  4. Теперь начните печатать i и увеличивайте его на LCM каждый раз после печати, пока оно не станет больше, чем R .

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

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

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