Horje
Find original Array from given Array of GCD of prefix

Given an array B[] of length N, the task is to print an array A[] such that for every ith element B[i] is gcd of the first i elements of A[] i.e. Bi = gcd (A1, A2, …., Ai) and if no such array A[] exists, print ?1.

Examples:

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.

Approach: The problem can be solved based on the following observation: 

  • 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.

Follow the below steps to solve the problem:

  • Initialize a boolean variable flag = true.
  • Iterate on the given array and check the following:
    • If the next element is not a factor of the current element:
      • Set flag = false.
      • Terminate the loop.
  • If the flag is true:
    • Print the given array B[].
    • else print -1.

Below is the implementation of the above approach.

C++

// C++ program for above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the original
// array from the modified array
void findOriginal(int arr[], int n)
{
 
  // Initialize flag as true
  bool flag = true;
 
  for (int i = 0; i < n - 1; i++) {
 
    // If the next element is not a
    // factor of current element
    if (arr[i] % arr[i + 1] != 0) {
      flag = false;
      break;
    }
  }
 
  if (flag == false)
    cout << "-1";;
  if (flag == true)
    for (int i =0;i<n;i++) {
      cout << arr[i] << " ";
    }
}
 
// Driver Code
int main()
{
 
  // Given input
  int B[] = { 4, 2 };
  int N = sizeof(B) / sizeof(B[0]);
 
  // Function call
  findOriginal(B, N);
 
  return 0;
}
 
// This code is contributed by code_hunt.

Java

// Java code to implement the approach
 
class GFG {
 
    // Function to find the original
    // array from the modified array
    static void findOriginal(int arr[], int n)
    {
 
        // Initialize flag as true
        boolean flag = true;
 
        for (int i = 0; i < n - 1; i++) {
 
            // If the next element is not a
            // factor of current element
            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 + " ");
            }
        }
    }
 
    // Driver code
    public static void main(String[] args)
    {
        // Given input
        int B[] = { 4, 2 };
        int N = B.length;
 
        // Function call
        findOriginal(B, N);
    }
}

C#

// C# code to implement the approach
using System;
public class GFG {
 
  // Function to find the original
  // array from the modified array
  static void findOriginal(int []arr, int n)
  {
 
    // Initialize flag as true
    bool flag = true;
 
    for (int i = 0; i < n - 1; i++) {
 
      // If the next element is not a
      // factor of current element
      if (arr[i] % arr[i + 1] != 0) {
        flag = false;
        break;
      }
    }
 
    if (flag == false)
      Console.WriteLine(-1);
    else {
      foreach (int val in arr) {
        Console.Write(val + " ");
      }
    }
  }
 
  // Driver code
  public static void Main(String[] args)
  {
    // Given input
    int []B = { 4, 2 };
    int N = B.Length;
 
    // Function call
    findOriginal(B, N);
  }
}
 
// This code is contributed by shikhasingrajput

Python3

# Python code to implement the approach
 
# Function to find the original
# array from the modified array
def findOriginal(arr, n):
  # Initialize flag as true
  flag = True
  i = 0
  for i in range(n-1):
    # If the next element is not a
    # factor of current element
    if (arr[i] % arr[i + 1] != 0):
      flag = False
      break
    else:
      i += 1
  if (flag == False):
    print(-1)
  else:
    for val in arr:
      print(val , end = " ")
# Driver code
# Given input
B = [4,2]
N = len(B)
# Function call
findOriginal(B, N)

Javascript

<script>
  // Javascript code to implement the approach
   
    // Function to find the original
    // array from the modified array
    function findOriginal(arr, n)
    {
 
        // Initialize flag as true
        let flag = true;
 
        for (let i = 0; i < n - 1; i++) {
 
            // If the next element is not a
            // factor of current element
            if (arr[i] % arr[i + 1] != 0) {
                flag = false;
                break;
            }
        }
 
        if (flag == false)
            document.write(-1);
        else {
            for (let val in arr) {
                document.write(arr[val] + " ");
            }
        }
    }
 
  // Driver code
           // Given input
        let B = [ 4, 2 ];
        let N = B.length;
 
        // Function call
        findOriginal(B, N);
   
  // This code is contributed by sanjoy_62.
  </script>

Output

4 2

Time Complexity: O(N) for traversing the given array.
Auxiliary Space: O(1) as constant space is used.


 


Reffered: https://www.geeksforgeeks.org

Arrays

Related
Count of Pairs such that modulo of product of one with their XOR and X is 1 Count of Pairs such that modulo of product of one with their XOR and X is 1
Check if Array can be made strictly increasing by replacing element with Average of adjacents Check if Array can be made strictly increasing by replacing element with Average of adjacents
Lexicographical smallest and largest Permutation from Array whose elements are max of Prefix Lexicographical smallest and largest Permutation from Array whose elements are max of Prefix
Minimize Array sum by replacing an element with GCD Minimize Array sum by replacing an element with GCD
Minimize operations to empty Array by deleting two unequal elements or one element Minimize operations to empty Array by deleting two unequal elements or one element

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 12



 

Horje