Найдите подмножество массива с заданным LCM

Учитывая массив arr[] , состоящий из N положительных целых чисел и положительного целого числа X , задача состоит в том, чтобы найти подмножество данного массива, чей наименьший общий кратный (НОК) равен X . Если подмножества не существует, выведите «-1» .

Примеры:

Input: arr[ ] = {2, 4, 3, 5}, X = 20
Output: {4, 5}
Explanation:
Consider the subset {4, 5}, the LCM of this subset is 20(= X). Therefore, print this subset.

Input: arr[ ] = {2, 3, 4, 5}, X = 18
Output: -1

Наивный подход: самый простой подход к решению данной проблемы состоит в том, чтобы найти все возможные подмножества данного массива, и если существует какое-либо подмножество, LCM которого равно X , то распечатать это подмножество. В противном случае выведите «-1» .

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

Эффективный подход. Описанный выше подход также можно оптимизировать, используя тот факт, что если элемент массива не является делителем X , то этот элемент не может быть включен в подмножество, поскольку LCM никогда не будет X . Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте переменную, скажем, LCM как 1 , которая хранит LCM результирующего подмножества.
• Инициализируйте вектор, скажем, subset[] , чтобы сохранить элемент массива, включенный в результирующее подмножество.
• Пройдите по заданному массиву arr[] и выполните следующие шаги:
  • Если текущий элемент является делителем X , то вставьте элемент в подмножество и возьмите LCM со значением LCM .
  • В противном случае продолжайте итерацию.
• После выполнения вышеуказанных шагов, если значение LCM равно X , выведите массив subset[] в качестве результирующего подмножества. В противном случае выведите «-1» .

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

Временная сложность: O(N*log M), где M — максимальный элемент массива .
Вспомогательное пространство: O(N)