Минимальная длина стержня, который может быть разделен на N равных частей, которые в дальнейшем могут быть разделены на заданное количество равных частей

Дан массив arr[] , состоящий из N положительных целых чисел. Задача состоит в том, чтобы найти минимально возможную длину стержня, который можно разрезать на N равных частей так, чтобы каждую i ^-ю часть можно было разрезать на arr[i] равных частей.

Примеры:

Input: arr[] = {1, 2}
Output: 4
Explanation:
Consider the length of the rod as 4. Then it can be divided in 2 equal parts, each having length 2.
Now, part 1 can be divided in arr[0](= 1) equal parts of length 2.
Part 2 can be divided in arr[1](= 2) equal parts of length 1.
Therefore, the minimum length of the rod must be 4.

Input: arr[] = {1, 1}
Output: 2

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

• Предположим, что минимальная длина стержня равна X , тогда этот стержень разрезается на N равных частей и длина каждой части будет X/N .
• Теперь каждые N частей снова будут урезаны следующим образом:
  • Часть 1 будет разрезана на arr[0] equal, где каждая часть имеет длину, скажем, a ₁ .
  • Часть 2 будет разрезана на arr[1] equal, где каждая часть имеет длину, скажем, a ₂ .
  • Часть 3 будет разрезана на arr[2] equal, где каждая часть имеет длину, скажем, a ₃ .
  • .
  • .
  • .
  • и так далее.
• Теперь приведенное выше соотношение можно также записать в виде:

X/N = arr[0]*a₁ = arr[1]*a₂ =  …  = arr[N – 1]*a_N.

• Следовательно, минимальная длина стержня определяется по формуле:

N*lcm (arr[0]*a₁, arr[1]*a₂, …, arr[N – 1]*a_N)

Из приведенных выше наблюдений выведите значение произведения N и НОК данного массива arr[] как результирующую минимальную длину стержня.

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

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