Найти исходный массив из заданного массива НОД префикса

Учитывая массив B[] длины N , задача состоит в том, чтобы напечатать массив A[] такой, что для каждого i- ^го элемента B[i] есть gcd первых i элементов A[] , т.е. B _i = gcd (A ₁ , A ₂ , …., A _i ) и если такого массива A[] не существует, выведите −1.

Примеры:

Input: B = {4, 2} 
Output: 4 2
Explanation: One possible answer is [4, 2] because 
B can be generated as follows: B=[gcd(4), gcd(4, 2)]=[4, 2].

Input: B = {2, 6, 8, 10} 
Output: -1
Explanation: No array exists which satisfies the given condition.

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

• We know that  B_i = gcd(A₁, A₂,  . . .  , A_i) and B_i+1 = gcd(A₁, A₂, . . ., A_i, A_i+1) = gcd(gcd(A₁, A₂, . . ., A_i), A_i+1) = gcd(B_i, A_i+1). This way, we can write B_i+1 = gcd(B_i , A_i+1).
• The implication of this is that B_i+1 must be a factor of B_i , Since gcd of two numbers is divisor of both numbers. Hence, condition B_i+1 divides B_i should hold for all 1 ≤ i <N.
• So if the given array has any such i where B_i+1 doesn’t divide B_i , no such A can exist.
• The given array B is a valid candidate for A as B_i+1 = gcd(B_i, A_i+1), but we have A_i+1 = B_i+1 . Since B_i+1 divide B_i , gcd(B_i, B_i+1) = B_i+1. So the given array B satisfies our condition and can be printed as array A.

Выполните следующие шаги, чтобы решить проблему:

• Инициализировать логическую переменную flag = true .
• Переберите заданный массив и проверьте следующее:
  • Если следующий элемент не является фактором текущего элемента:
    • Установить флаг = ложь .
    • Завершите цикл.
• Если флаг верен:
  • Выведите заданный массив B[] .
  • иначе напечатайте -1.

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

Сложность времени: O(N) для обхода заданного массива.
Вспомогательное пространство: используется O(1) в качестве постоянного пространства.