Найти исходный массив из заданного массива НОД префикса
Учитывая массив 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) в качестве постоянного пространства.