# Discover unique 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 ith factor B[i] is gcd of the primary i components of A[] i.e. Bi = gcd (A1, A2, …., Ai) and if no such array A[] exists, print −1.

Examples:

Enter: B = {4, 2}
Output: 4 2
Rationalization: One doable 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
Rationalization: No array exists which satisfies the given situation.

Strategy: The issue may be solved primarily based on the next commentary:

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

Observe the beneath steps to resolve the issue:

• Initialize a boolean variable flag = true.
• Iterate on the given array and examine the next:
• If the subsequent factor isn’t an element of the present factor:
• 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 strategy.

## Java

 ` `  `class` `GFG {` ` `  `    ` `    ` `    ``static` `void` `findOriginal(``int` `arr[], ``int` `n)` `    ``{` ` `  `        ` `        ``boolean` `flag = ``true``;` ` `  `        ``for` `(``int` `i = ``0``; i < n - ``1``; i++) {` ` `  `            ` `            ` `            ``if` `(arr[i] % arr[i + ``1``] != ``0``) {` `                ``flag = ``false``;` `                ``break``;` `            ``}` `        ``}` ` `  `        ``if` `(flag == ``false``)` `            ``System.out.println(-``1``);` `        ``else` `{` `            ``for` `(``int` `val : arr) {` `                ``System.out.print(val + ``" "``);` `            ``}` `        ``}` `    ``}` ` `  `    ` `    ``public` `static` `void` `principal(String[] args)` `    ``{` `        ` `        ``int` `B[] = { ``4``, ``2` `};` `        ``int` `N = B.size;` ` `  `        ` `        ``findOriginal(B, N);` `    ``}` `}`

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

Latest articles

Related articles