Наибольшее K-значное число, которое делится на все числа в данном массиве

Дан массив arr[] размера N и целое число K. Задача состоит в том, чтобы найти наибольшее число K цифр , которое делится на все числа arr[].

Примеры:

Input: arr[] = {2, 3, 5}, K = 3
Output: 990
Explanation: 990 is the largest 3 digit number divisible by 2, 3 and 5.

Input: arr[] = {91, 93, 95}, K = 3
Output: -1
Explanation: There is no 3 digit number divisible by all 91, 93 and 95.

Подход: Решение основано на идее, аналогичной поиску наибольшего K-значного числа, которое делится на X. Выполните шаги, указанные ниже.

• Найти НОК всех чисел массива arr[]
• Найдите наибольшее кратное LCM, содержащее K цифр, по формуле:

LCM(arr) * ((10^K-1)/LCM(arr))

Ниже приведена реализация описанного выше подхода.

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