Discover authentic 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 ingredient 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
Rationalization: One attainable reply is [4, 2] as a result of 
B could be generated as follows: B=[gcd(4), gcd(4, 2)]=[4, 2].

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

Strategy: The issue could be solved primarily based on the next statement: 

• 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 manner, we are able to write B_i+1 = gcd(B_i , A_i+1).
• The implication of that is that B_i+1 should 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 now 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 situation and could be printed as array A.

Observe the under steps to unravel the issue:

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

Beneath is the implementation of the above method.

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