Dadas dos arrays A[] y B[], ambas de tamaño N , la tarea es generar una secuencia de longitud N que comprenda elementos de las dos arrays, de modo que el GCD de la secuencia generada sea K. Si no es posible generar tal secuencia, imprima «-1» .
Ejemplos:
Entrada: A[] = {5, 3, 6, 2, 9}, B[] = {21, 7, 14, 12, 28}, K = 3
Salida: 21, 3, 6, 12, 9
Explicación:
respuesta[0] = 21 (= B[0])
respuesta[1] = 3 (= A[1])
respuesta[2] = 6 (= A[2])
respuesta[3] = 12 (= B[3 ])
ans[4] = 9 (= A[4])
Por lo tanto, el MCD de la secuencia generada es {21, 3, 6, 12, 9} es 3.Entrada: A[] = {3, 4, 5, 6, 7}, B[] = {8, 7, 5, 2, 3}, K = 2
Salida: -1
Enfoque ingenuo: el enfoque más simple para resolver el problema es usar Recursion . Comprueba recursivamente todas las combinaciones posibles de las condiciones dadas.
Siga los pasos a continuación para resolver el problema:
- Defina una función para generar recursivamente todas las combinaciones posibles y realice los siguientes pasos:
- La condición base es cuando la longitud de la combinación actual es igual a N y verificar si el GCD de la combinación actual es igual a K.
- Si el GCD es igual a K , imprima la combinación y devuelva True . De lo contrario, devuelve False .
- Agregue un elemento de la array A[] a la combinación y continúe.
- Elimina el elemento agregado después de la llamada recursiva.
- Agregue un elemento de la array B[] a la combinación y continúe.
- Elimina el elemento agregado después de la llamada recursiva.
- Si GCD no es igual a K para ninguna combinación, imprima -1.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate
// GCD of two integers
int GCD(int a, int b)
{
if (!b)
return a;
return GCD(b, a % b);
}
// Function to calculate
// GCD of a given array
int GCDArr(vector<int> a)
{
int ans = a[0];
for (int i:a)
ans = GCD(ans, i);
return ans;
}
// Utility function to check for
// all the possible combinations
bool findSubseqUtil(vector<int> a,vector<int> b,
vector<int> &ans,int k,int i)
{
// If an N-length sequence
// is obtained
if (ans.size() == a.size())
{
// If GCD of the sequence is K
if (GCDArr(ans) == k)
{
cout << "[";
int m = ans.size();
for(int i = 0; i < m - 1; i++)
cout << ans[i] << ", ";
cout << ans[m - 1] << "]";
return true;
}
// Otherwise
else
return false;
}
// Add an element from the first array
ans.push_back(a[i]);
// Recursively proceed further
bool temp = findSubseqUtil(a, b, ans, k, i + 1);
// If combination satisfies
// the necessary condition
if (temp)
return true;
// Remove the element
// from the combination
ans.pop_back();
// Add an element from the second array
ans.push_back(b[i]);
// Recursive proceed further
temp = findSubseqUtil(a, b, ans, k, i + 1);
// If combination satisfies
// the necessary condition
if (temp)
return true;
// Remove the element
// from the combination
ans.pop_back();
return false;
}
// Function to check all the
// possible combinations
void findSubseq(vector<int> A, vector<int> B,
int K, int i)
{
// Stores the subsequence
vector<int> ans;
findSubseqUtil(A, B, ans, K, i);
// If GCD is not equal to K
// for any combination
if (!ans.size())
cout << -1;
}
// Driver Code
int main()
{
// Given arrays
vector<int> A = {5, 3, 6, 2, 9};
vector<int> B = {21, 7, 14, 12, 28};
// Given value of K
int K = 3;
// Function call to generate
// the required subsequence
findSubseq(A, B, K, 0);
return 0;
}
// This code is contributed by mohit kumar 29.
Java
// Java program for the above approach
import java.util.*;
import java.lang.*;
class GFG
{
// Function to calculate
// GCD of two integers
static int GCD(int a, int b)
{
if (b < 1)
return a;
return GCD(b, a % b);
}
// Function to calculate
// GCD of a given array
static int GCDArr(ArrayList<Integer> a)
{
int ans = a.get(0);
for(int i : a) ans = GCD(ans, i);
return ans;
}
// Utility function to check for
// all the possible combinations
static boolean findSubseqUtil(ArrayList<Integer> a, ArrayList<Integer> b,
ArrayList<Integer> ans, int k, int i)
{
// If an N-length sequence
// is obtained
if (ans.size() == a.size()) {
// If GCD of the sequence is K
if (GCDArr(ans) == k) {
System.out.print("[");
int m = ans.size();
for (int j = 0; j < m - 1; j++)
System.out.print(ans.get(j) + ", ");
System.out.print(ans.get(m-1) + "]");
return true;
}
// Otherwise
else
return false;
}
// Add an element from the first array
ans.add(a.get(i));
// Recursively proceed further
boolean temp = findSubseqUtil(a, b, ans, k, i + 1);
// If combination satisfies
// the necessary condition
if (temp)
return true;
// Remove the element
// from the combination
ans.remove(ans.size() - 1);
// Add an element from the second array
ans.add(b.get(i));
// Recursive proceed further
temp = findSubseqUtil(a, b, ans, k, i + 1);
// If combination satisfies
// the necessary condition
if (temp)
return true;
// Remove the element
// from the combination
ans.remove(ans.size() - 1);
return false;
}
// Function to check all the
// possible combinations
static void findSubseq(ArrayList<Integer> A, ArrayList<Integer> B, int K,
int i)
{
// Stores the subsequence
ArrayList<Integer> ans = new ArrayList<Integer>();
findSubseqUtil(A, B, ans, K, i);
// If GCD is not equal to K
// for any combination
if (ans.size() < 1)
System.out.println(-1);
}
// Driver code
public static void main(String[] args)
{
// Given arrays
ArrayList<Integer> A = new ArrayList<>();
A.add(5);
A.add(3);
A.add(6);
A.add(2);
A.add(9);
ArrayList<Integer> B = new ArrayList<Integer>();
B.add(21);
B.add(7);
B.add(14);
B.add(12);
B.add(28);
// Given value of K
int K = 3;
// Function call to generate
// the required subsequence
findSubseq(A, B, K, 0);
}
}
// This code is contributed by sanjoy_62.
Python3
# Python3 program for the above approach # Function to calculate # GCD of two integers def GCD(a, b): if not b: return a return GCD(b, a % b) # Function to calculate # GCD of a given array def GCDArr(a): ans = a[0] for i in a: ans = GCD(ans, i) return ans # Utility function to check for # all the possible combinations def findSubseqUtil(a, b, ans, k, i): # If an N-length sequence # is obtained if len(ans) == len(a): # If GCD of the sequence is K if GCDArr(ans) == k: print(ans) return True # Otherwise else: return False # Add an element from the first array ans.append(a[i]) # Recursively proceed further temp = findSubseqUtil(a, b, ans, k, i+1) # If combination satisfies # the necessary condition if temp == True: return True # Remove the element # from the combination ans.pop() # Add an element from the second array ans.append(b[i]) # Recursive proceed further temp = findSubseqUtil(a, b, ans, k, i+1) # If combination satisfies # the necessary condition if temp == True: return True # Remove the element # from the combination ans.pop() # Function to check all the # possible combinations def findSubseq(A, B, K, i): # Stores the subsequence ans = [] findSubseqUtil(A, B, ans, K, i) # If GCD is not equal to K # for any combination if not ans: print(-1) # Driver Code # Given arrays A = [5, 3, 6, 2, 9] B = [21, 7, 14, 12, 28] # Given value of K K = 3 # Function call to generate # the required subsequence ans = findSubseq(A, B, K, 0)
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to calculate
// GCD of two integers
static int GCD(int a, int b)
{
if (b < 1)
return a;
return GCD(b, a % b);
}
// Function to calculate
// GCD of a given array
static int GCDArr(List<int> a)
{
int ans = a[0];
foreach(int i in a) ans = GCD(ans, i);
return ans;
}
// Utility function to check for
// all the possible combinations
static bool findSubseqUtil(List<int> a, List<int> b,
List<int> ans, int k, int i)
{
// If an N-length sequence
// is obtained
if (ans.Count == a.Count) {
// If GCD of the sequence is K
if (GCDArr(ans) == k) {
Console.Write("[");
int m = ans.Count;
for (int j = 0; j < m - 1; j++)
Console.Write(ans[j] + ", ");
Console.Write(ans[m - 1] + "]");
return true;
}
// Otherwise
else
return false;
}
// Add an element from the first array
ans.Add(a[i]);
// Recursively proceed further
bool temp = findSubseqUtil(a, b, ans, k, i + 1);
// If combination satisfies
// the necessary condition
if (temp)
return true;
// Remove the element
// from the combination
ans.RemoveAt(ans.Count - 1);
// Add an element from the second array
ans.Add(b[i]);
// Recursive proceed further
temp = findSubseqUtil(a, b, ans, k, i + 1);
// If combination satisfies
// the necessary condition
if (temp)
return true;
// Remove the element
// from the combination
ans.RemoveAt(ans.Count - 1);
return false;
}
// Function to check all the
// possible combinations
static void findSubseq(List<int> A, List<int> B, int K,
int i)
{
// Stores the subsequence
List<int> ans = new List<int>();
findSubseqUtil(A, B, ans, K, i);
// If GCD is not equal to K
// for any combination
if (ans.Count < 1)
Console.WriteLine(-1);
}
// Driver Code
public static void Main()
{
// Given arrays
List<int> A = new List<int>{ 5, 3, 6, 2, 9 };
List<int> B = new List<int>{ 21, 7, 14, 12, 28 };
// Given value of K
int K = 3;
// Function call to generate
// the required subsequence
findSubseq(A, B, K, 0);
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript program for the above approach
// Function to calculate
// GCD of two integers
function GCD(a,b)
{
if (b < 1)
return a;
return GCD(b, a % b);
}
// Function to calculate
// GCD of a given array
function GCDArr(a)
{
let ans = a[0];
for(let i=0;i<a.length;i++)
ans = GCD(ans, a[i]);
return ans;
}
// Utility function to check for
// all the possible combinations
function findSubseqUtil(a,b,ans,k,i)
{
// If an N-length sequence
// is obtained
if (ans.length == a.length) {
// If GCD of the sequence is K
if (GCDArr(ans) == k) {
document.write("[");
let m = ans.length;
for (let j = 0; j < m - 1; j++)
document.write(ans[j] + ", ");
document.write(ans[m-1] + "]");
return true;
}
// Otherwise
else
return false;
}
// Add an element from the first array
ans.push(a[i]);
// Recursively proceed further
let temp = findSubseqUtil(a, b, ans, k, i + 1);
// If combination satisfies
// the necessary condition
if (temp)
return true;
// Remove the element
// from the combination
ans.splice(ans.length - 1,1);
// Add an element from the second array
ans.push(b[i]);
// Recursive proceed further
temp = findSubseqUtil(a, b, ans, k, i + 1);
// If combination satisfies
// the necessary condition
if (temp)
return true;
// Remove the element
// from the combination
ans.splice(ans.length - 1,1);
return false;
}
// Function to check all the
// possible combinations
function findSubseq(A,B,K,i)
{
// Stores the subsequence
let ans = [];
findSubseqUtil(A, B, ans, K, i);
// If GCD is not equal to K
// for any combination
if (ans.length < 1)
document.write(-1);
}
// Driver code
// Given arrays
let A = [5, 3, 6, 2, 9];
let B = [21, 7, 14, 12, 28];
// Given value of K
let K = 3;
// Function call to generate
// the required subsequence
findSubseq(A, B, K, 0);
// This code is contributed by patel2127
</script>
Producción:
[21, 3, 6, 12, 9]
Complejidad de Tiempo: O(2 N * N * logN)
Espacio Auxiliar: O(N)
Enfoque eficiente: para optimizar el enfoque anterior, siga los pasos a continuación para resolver el problema:
- El MCD de la sucesión será igual a K , sólo si todos los elementos presentes en la sucesión son divisibles por K .
- Atraviese las arrays simultáneamente y realice los siguientes pasos:
- Compruebe si el elemento actual en la array A[] es divisible por K . Si se encuentra que es cierto, entonces haga una llamada recursiva. De lo contrario, devuelve falso.
- Compruebe si el elemento actual en la array B[] es divisible por K . Si se encuentra que es cierto, entonces haga una llamada recursiva. De lo contrario, devuelve falso .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
int GCD(int a, int b)
{
if (b == 0)
return a;
return GCD(b, a % b);
}
// Function to calculate
// GCD of given array
int GCDArr(vector<int> a)
{
int ans = a[0];
for(auto val : a)
{
ans = GCD(ans, val);
}
return ans;
}
// Utility function to check for
// all the combinations
bool findSubseqUtil(int a[], int b[], vector<int> ans,
int k, int i, int N)
{
// If a sequence of size N
// is obtained
if (ans.size() == N)
{
// If gcd of current
// combination is K
if (GCDArr(ans) == k)
{
for(auto val : ans)
cout << val << " ";
return true;
}
else
{
return false;
}
}
// If current element from
// first array is divisible by K
if (a[i] % k == 0)
{
ans.push_back(a[i]);
// Recursively proceed further
bool temp = findSubseqUtil(a, b, ans, k,
i + 1, N);
// If current combination
// satisfies given condition
if (temp == true)
return true;
// Remove the element
// from the combination
ans.pop_back();
}
// If current element from
// second array is divisible by K
if (b[i] % k == 0)
{
ans.push_back(b[i]);
// Recursively proceed further
bool temp = findSubseqUtil(a, b, ans, k,
i + 1, N);
// If current combination
// satisfies given condition
if (temp == true)
return true;
// Remove the element
// from the combination
ans.pop_back();
}
return false;
}
// Function to check for all
// possible combinations
void findSubseq(int A[], int B[], int K,
int i, int N)
{
// Stores the subsequence
vector<int> ans;
bool ret = findSubseqUtil(A, B, ans,
K, i, N);
// If GCD of any sequence
// is not equal to K
if (ret == false)
cout << -1 << "\n";
}
// Driver Code
int main()
{
// Given arrays
int A[] = { 5, 3, 6, 2, 9 };
int B[] = { 21, 7, 14, 12, 28 };
// size of the array
int N = sizeof(A) / sizeof(A[0]);
// Given value of K
int K = 3;
// Function call to generate a
// subsequence whose GCD is K
findSubseq(A, B, K, 0, N);
return 0;
}
// This code is contributed by Kingash
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG{
static int GCD(int a, int b)
{
if (b == 0)
return a;
return GCD(b, a % b);
}
// Function to calculate
// GCD of given array
static int GCDArr(ArrayList<Integer> a)
{
int ans = a.get(0);
for(int val : a)
{
ans = GCD(ans, val);
}
return ans;
}
// Utility function to check for
// all the combinations
static boolean findSubseqUtil(int a[], int b[],
ArrayList<Integer> ans,
int k, int i)
{
// If a sequence of size N
// is obtained
if (ans.size() == a.length)
{
// If gcd of current
// combination is K
if (GCDArr(ans) == k)
{
System.out.println(ans);
return true;
}
else
{
return false;
}
}
// If current element from
// first array is divisible by K
if (a[i] % k == 0)
{
ans.add(a[i]);
// Recursively proceed further
boolean temp = findSubseqUtil(a, b, ans,
k, i + 1);
// If current combination
// satisfies given condition
if (temp == true)
return true;
// Remove the element
// from the combination
ans.remove(ans.size() - 1);
}
// If current element from
// second array is divisible by K
if (b[i] % k == 0)
{
ans.add(b[i]);
// Recursively proceed further
boolean temp = findSubseqUtil(a, b, ans,
k, i + 1);
// If current combination
// satisfies given condition
if (temp == true)
return true;
// Remove the element
// from the combination
ans.remove(ans.size() - 1);
}
return false;
}
// Function to check for all
// possible combinations
static void findSubseq(int A[], int B[],
int K, int i)
{
// Stores the subsequence
ArrayList<Integer> ans = new ArrayList<>();
boolean ret = findSubseqUtil(A, B, ans, K, i);
// If GCD of any sequence
// is not equal to K
if (ret == false)
System.out.println(-1);
}
// Driver Code
public static void main(String[] args)
{
// Given arrays
int A[] = { 5, 3, 6, 2, 9 };
int B[] = { 21, 7, 14, 12, 28 };
// Given value of K
int K = 3;
// Function call to generate a
// subsequence whose GCD is K
findSubseq(A, B, K, 0);
}
}
// This code is contributed by Kingash
Python3
# Python3 program for the above approach # Function to calculate # GCD of two integers def GCD(a, b): if not b: return a return GCD(b, a % b) # Function to calculate # GCD of given array def GCDArr(a): ans = a[0] for i in a: ans = GCD(ans, i) return ans # Utility function to check for # all the combinations def findSubseqUtil(a, b, ans, k, i): # If a sequence of size N # is obtained if len(ans) == len(a): # If gcd of current # combination is K if GCDArr(ans) == k: print(ans) return True else: return False # If current element from # first array is divisible by K if not a[i] % K: ans.append(a[i]) # Recursively proceed further temp = findSubseqUtil(a, b, ans, k, i+1) # If current combination # satisfies given condition if temp == True: return True # Remove the element # from the combination ans.pop() # If current element from # second array is divisible by K if not b[i] % k: ans.append(b[i]) # Recursively proceed further temp = findSubseqUtil(a, b, ans, k, i+1) # If current combination # satisfies given condition if temp == True: return True # Remove the element # from the combination ans.pop() return False # Function to check for all # possible combinations def findSubseq(A, B, K, i): # Stores the subsequence ans = [] findSubseqUtil(A, B, ans, K, i) # If GCD of any sequence # is not equal to K if not ans: print(-1) # Driver Code # Given arrays A = [5, 3, 6, 2, 9] B = [21, 7, 14, 12, 28] # Given value of K K = 3 # Function call to generate a # subsequence whose GCD is K ans = findSubseq(A, B, K, 0)
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
static int GCD(int a, int b)
{
if (b == 0)
return a;
return GCD(b, a % b);
}
// Function to calculate
// GCD of given array
static int GCDArr(List<int> a)
{
int ans = a[0];
foreach (int val in a)
{
ans = GCD(ans, val);
}
return ans;
}
// Utility function to check for
// all the combinations
static bool findSubseqUtil(int []a, int []b, List<int> ans,
int k, int i, int N)
{
// If a sequence of size N
// is obtained
if (ans.Count == N)
{
// If gcd of current
// combination is K
if (GCDArr(ans) == k)
{
foreach(int val in ans)
Console.Write(val+" ");
return true;
}
else
{
return false;
}
}
// If current element from
// first array is divisible by K
if (a[i] % k == 0)
{
ans.Add(a[i]);
// Recursively proceed further
bool temp = findSubseqUtil(a, b, ans, k,
i + 1, N);
// If current combination
// satisfies given condition
if (temp == true)
return true;
// Remove the element
// from the combination
ans.RemoveAt(ans.Count - 1);
}
// If current element from
// second array is divisible by K
if (b[i] % k == 0)
{
ans.Add(b[i]);
// Recursively proceed further
bool temp = findSubseqUtil(a, b, ans, k,
i + 1, N);
// If current combination
// satisfies given condition
if (temp == true)
return true;
// Remove the element
// from the combination
ans.RemoveAt(ans.Count - 1);
}
return false;
}
// Function to check for all
// possible combinations
static void findSubseq(int []A, int []B, int K,
int i, int N)
{
// Stores the subsequence
List<int> ans = new List<int>();
bool ret = findSubseqUtil(A, B, ans,
K, i, N);
// If GCD of any sequence
// is not equal to K
if (ret == false)
Console.Write(-1);
}
// Driver Code
public static void Main()
{
// Given arrays
int []A = { 5, 3, 6, 2, 9 };
int []B = { 21, 7, 14, 12, 28 };
// size of the array
int N = A.Length;
// Given value of K
int K = 3;
// Function call to generate a
// subsequence whose GCD is K
findSubseq(A, B, K, 0, N);
}
}
// This code is contributed by ipg2016107.
Javascript
<script>
// JavaScript program for the above approach
function GCD(a, b) {
if (b === 0) return a;
return GCD(b, a % b);
}
// Function to calculate
// GCD of given array
function GCDArr(a) {
var ans = a[0];
for (const val of a) {
ans = GCD(ans, val);
}
return ans;
}
// Utility function to check for
// all the combinations
function findSubseqUtil(a, b, ans, k, i, N) {
// If a sequence of size N
// is obtained
if (ans.length === N) {
// If gcd of current
// combination is K
if (GCDArr(ans) === k) {
document.write("[" + ans + "]");
return true;
} else {
return false;
}
}
// If current element from
// first array is divisible by K
if (a[i] % k === 0) {
ans.push(a[i]);
// Recursively proceed further
var temp = findSubseqUtil(a, b, ans, k, i + 1, N);
// If current combination
// satisfies given condition
if (temp === true) return true;
// Remove the element
// from the combination
delete ans[ans.length - 1];
}
// If current element from
// second array is divisible by K
if (b[i] % k === 0) {
ans.push(b[i]);
// Recursively proceed further
var temp = findSubseqUtil(a, b, ans, k, i + 1, N);
// If current combination
// satisfies given condition
if (temp === true) return true;
// Remove the element
// from the combination
delete ans[ans.length - 1];
}
return false;
}
// Function to check for all
// possible combinations
function findSubseq(A, B, K, i, N) {
// Stores the subsequence
var ans = [];
var ret = findSubseqUtil(A, B, ans, K, i, N);
// If GCD of any sequence
// is not equal to K
if (ret === false) document.write(-1);
}
// Driver Code
// Given arrays
var A = [5, 3, 6, 2, 9];
var B = [21, 7, 14, 12, 28];
// size of the array
var N = A.length;
// Given value of K
var K = 3;
// Function call to generate a
// subsequence whose GCD is K
findSubseq(A, B, K, 0, N);
</script>
Producción:
[21, 3, 6, 12, 9]
Complejidad de Tiempo: O(2 N * N * logN)
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por rohitsingh07052 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA