Find the array B[] from A[] according to the given conditions
Given an array X[] of length N, having all elements less than or equal to M, the task is to print an array let’s say Y[] of the same length following the given conditions:
- Prefix GCD till index i in Y[] must be equal to ith element of X[] for all i (0 <= i <= N-1)
- The output array must be lexographically largest.
- The upper bound for all elements of Y[] is M. Formally, elements of Y[] must be less than or equal to M.
Examples:
Input: N = 4, M = 5, X[] = {2, 2, 2, 2}
Output: Y[] = {2, 4, 4, 4}
Explanation:
- Till index 0: GCD(2) = X[0] = 2.
- Till index 1: GCD(2, 4) = X[1] = 2.
- Till index 2: GCD(2, 4, 4) = X[2] = 2.
- Till index 3: GCD(2, 4, 4, 4) = X[3] = 2.
It can be verified that all the elements of Y[] are also less than or equal to M along with this Y[] is lexographically large as possible. Thus, Y[] follows all the given conditions.
Input: N = 6, M = 7, X[] = {3, 6, 1, 4, 3, 6}
Output: Y[] = {3, 0, 7, 0, 0, 0}
Explanation: It can be verified that the Y[] is lexographically largest possible following all the given conditions.
Approach:
The problem is based on the Number Theory and can be solve using some observations. Let us discuss the observations and approach to solve out this problem.
Here, by reading the problem, First observation that comes to mind is that, If first element of Y[i] will be equal to X[i]. Only then, GCD(Y[0] = X[0]. Therefore, we know that Y[0] must be equal to X[0].
For remaining terms, We need to find the largest number let say num, that is less than or equal to M , such that GCD (num, X[i-1]) = X[i]. So we find the maximum number which is <=M and is a multiple of X[i] in next step of approach.
For doing so, we will iterate from it to back, to find the number which satisfy our condition. If we get the number which satisfy our conditions we assign it to Y[i] and break.
Step-by-step approach:
- First, initialize array Y[] with all elements as 0 and set Y[0] equal to X[0].
- For each element X[i] from i = 1 to N-1, We have calculate the maximum multiple of X[i] that is less than or equal to M. This is done by dividing M by X[i] and multiplying the result by X[i].
- Starting from this maximum multiple, it checks each multiple of X[i] in decreasing order to find a value that, when combined with X[i-1], gives a GCD equal to X[i]. This is done using the GCD function in Java (BigInteger.valueOf(j).gcd(BigInteger.valueOf(X[i-1]))). The first such value found is assigned to Y[i].
- Finally, it prints out the elements of array Y.
Below is the implementation of the above approach:
C++
#include <iostream> #include <vector> #include <algorithm> #include <numeric> using namespace std; // Function to find array Y void Find_array( int N, int M, vector< int >& X) { vector< int > Y(N); Y[0] = X[0]; // Loop for each element from the second to the last for ( int i = 1; i < N; i++) { // Calculate the maximum multiple of X[i] that // is less than or equal to M int x = (M / X[i]) * X[i]; // Check each multiple of X[i] in decreasing order for ( int j = x; j >= 0; j -= X[i]) { // Calculate the gcd of j and X[i-1] int gcd = __gcd(j, X[i - 1]); // If the gcd is equal to X[i], assign j to // Y[i] and break the loop if (gcd == X[i]) { Y[i] = j; break ; } } } // Print out the elements of array Y for ( int i = 0; i < N; i++) cout << Y[i] << " " ; cout << endl; } // Driver function int main() { // Inputs int N = 4; int M = 5; vector< int > X = { 2, 2, 2, 2 }; // Function call Find_array(N, M, X); return 0; } |
Java
// Java code to implement the approach // Necessary Libraries import java.math.BigInteger; import java.util.Scanner; // Driver Class class Main { // Driver Function public static void main(String[] args) { // Inputs int N = 4 ; int M = 5 ; int [] X = { 2 , 2 , 2 , 2 }; // Function call Find_array(N, M, X); } // Method to output Y[] public static void Find_array( int N, int M, int [] X) { int [] Y = new int [N]; Y[ 0 ] = X[ 0 ]; // Loop for each element from the second to the last for ( int i = 1 ; i < N; i++) { // Calculate the maximum multiple of X[i] that // is less than or equal to M int x = (M / X[i]) * X[i]; // Check each multiple of X[i] in decreasing // order for ( int j = x; j >= 0 ; j -= X[i]) { // Calculate the gcd of j and X[i-1] BigInteger gcd = BigInteger.valueOf(j).gcd( BigInteger.valueOf(X[i - 1 ])); // If the gcd is equal to X[i], assign j to // Y[i] and break the loop if (gcd.intValue() == X[i]) { Y[i] = j; break ; } } } // Print out the elements of array Y for ( int i = 0 ; i < N; i++) System.out.print(Y[i] + " "); System.out.println(); } } |
Python3
# Python Implementation import math # Function to find array Y def find_array(N, M, X): Y = [ 0 ] * N Y[ 0 ] = X[ 0 ] # Loop for each element from the second to the last for i in range ( 1 , N): # Calculate the maximum multiple of X[i] that # is less than or equal to M x = (M / / X[i]) * X[i] # Check each multiple of X[i] in decreasing order for j in range (x, - 1 , - X[i]): # Calculate the gcd of j and X[i-1] gcd_val = math.gcd(j, X[i - 1 ]) # If the gcd is equal to X[i], assign j to # Y[i] and break the loop if gcd_val = = X[i]: Y[i] = j break # Print out the elements of array Y print ( * Y) # Driver function if __name__ = = "__main__" : # Inputs N = 4 M = 5 X = [ 2 , 2 , 2 , 2 ] # Function call find_array(N, M, X) # This code is contributed by Sakshi |
C#
using System; using System.Collections.Generic; class Program { // Function to find array Y static void FindArray( int N, int M, List< int > X) { List< int > Y = new List< int >(N); Y.Add(X[0]); // Loop for each element from the second to the last for ( int i = 1; i < N; i++) { // Calculate the maximum multiple of X[i] that // is less than or equal to M int x = (M / X[i]) * X[i]; // Check each multiple of X[i] in decreasing // order for ( int j = x; j >= 0; j -= X[i]) { // Calculate the gcd of j and X[i-1] int gcd = GCD(j, X[i - 1]); // If the gcd is equal to X[i], assign j to // Y[i] and break the loop if (gcd == X[i]) { Y.Add(j); break ; } } } // Print out the elements of array Y foreach ( var y in Y) Console.Write(y + " " ); Console.WriteLine(); } // Function to calculate the gcd of two numbers static int GCD( int a, int b) { while (b != 0) { int temp = b; b = a % b; a = temp; } return a; } // Driver function static void Main() { // Inputs int N = 4; int M = 5; List< int > X = new List< int >{ 2, 2, 2, 2 }; // Function call FindArray(N, M, X); } } |
Javascript
// Function to find array Y function findArray(N, M, X) { const Y = new Array(N); Y[0] = X[0]; // Loop for each element from the second to the last for (let i = 1; i < N; i++) { // Calculate the maximum multiple of X[i] that // is less than or equal to M let x = Math.floor(M / X[i]) * X[i]; // Check each multiple of X[i] in decreasing order for (let j = x; j >= 0; j -= X[i]) { // Calculate the gcd of j and X[i-1] let gcd = gcdFunction(j, X[i - 1]); // If the gcd is equal to X[i], assign j to // Y[i] and break the loop if (gcd === X[i]) { Y[i] = j; break ; } } } // Print out the elements of array Y console.log(Y.join( " " )); } // GCD (Greatest Common Divisor) function function gcdFunction(a, b) { return b === 0 ? a : gcdFunction(b, a % b); } // Driver function function main() { // Inputs const N = 4; const M = 5; const X = [2, 2, 2, 2]; // Function call findArray(N, M, X); } // Call the main function main(); |
2 4 4 4
Time Complexity: O(N*M)
Auxiliary Space: O(1)