Wednesday, August 31, 2022
HomeWordPress DevelopmentDiscover authentic Array from given Array of GCD of prefix

Discover authentic Array from given Array of GCD of prefix


View Dialogue

Enhance Article

Save Article

Like Article

View Dialogue

Enhance Article

Save Article

Like Article

Given an array B[] of size N, the duty is to print an array A[] such that for each ith ingredient 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 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  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 are able to write Bi+1 = gcd(Bi , Ai+1).
  • The implication of that is that Bi+1 should 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 now we have Ai+1 = Bi+1 . Since Bi+1 divide Bi , gcd(Bi, Bi+1) = Bi+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.

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 Area: O(1) as fixed house is used.

RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

- Advertisment -
Google search engine

Most Popular

Recent Comments