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

Опубликовано: 25 Февраля, 2023

Учитывая массив B[] длины N , задача состоит в том, чтобы напечатать массив A[] такой, что для каждого i- го элемента B[i] есть gcd первых i элементов A[] , т.е. B i = gcd (A 1 , A 2 , …., 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  Bi = gcd(A1, A2,  . . .  , Ai) and Bi+1 = gcd(A1, A2, . . ., Ai, Ai+1) = gcd(gcd(A1, A2, . . ., Ai), Ai+1) = gcd(Bi, Ai+1). This way, we can write Bi+1 = gcd(Bi , Ai+1).
  • The implication of this is that Bi+1 must be a factor of Bi , Since gcd of two numbers is divisor of both numbers. Hence, condition Bi+1 divides Bi should hold for all 1 ≤ i <N.
  • So if the given array has any such i where Bi+1 doesn’t divide Bi , no such A can exist.
  • The given array B is a valid candidate for A as Bi+1 = gcd(Bi, Ai+1), but we have Ai+1 = Bi+1 . Since Bi+1 divide Bi , gcd(Bi, Bi+1) = Bi+1. So the given array B satisfies our condition and can be printed as array A.

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

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

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

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

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