Find original Array from given Array of GCD of prefix

Given an array B[] of size N, the duty is to print an array A[] such that for each i^th aspect B[i] is gcd of the primary i components of A[] i.e. B_i = gcd (A₁, A₂, …., A_i) and if no such array A[] exists, print −1.

Examples:

Enter: B = {4, 2} 
Output: 4 2
Clarification: One attainable reply is [4, 2] as a result of 
B may be generated as follows: B=[gcd(4), gcd(4, 2)]=[4, 2].

Enter: B = {2, 6, 8, 10} 
Output: -1
Clarification: No array exists which satisfies the given situation.

Method: The issue may be solved based mostly on the next remark: 

• We all 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 fashion, we will write B_i+1 = gcd(B_i , A_i+1).
• The implication of that is that B_i+1 have to be an element of B_i , Since gcd of two numbers is divisor of each numbers. Therefore, situation B_i+1 divides B_i ought to maintain for all 1 ≤ i <N.
• So if the given array has any such i the place B_i+1 doesn’t divide B_i , no such A can exist.
• The given array B is a sound candidate for A as B_i+1 = gcd(B_i, A_i+1), however we’ve got 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 situation and may be printed as array A.

Observe the beneath steps to unravel the issue:

• Initialize a boolean variable flag = true.
• Iterate on the given array and verify the next:
  • If the subsequent aspect shouldn’t be an element of the present aspect:
    • Set flag = false.
    • Terminate the loop.
• If the flag is true:
  • Print the given array B[].
  • else print -1.

Under is the implementation of the above strategy.

Time Complexity: O(N) for traversing the given array.
Auxiliary Area: O(1) as fixed house is used.