Dada una array arr[] de tamaño N , la tarea es encontrar la subsecuencia más pequeña de la array dada cuyo GCD de la subsecuencia es igual al GCD de la array dada . Si existe más de una de esas subsecuencias, imprima cualquiera de ellas.
Ejemplos:
Entrada: arr[] = {4, 6, 12}
Salida: 4 6
Explicación: La subsecuencia más pequeña que tiene gcd igual a gcd de la array dada (= 2) es {4, 6}. Por lo tanto, la salida requerida es {4, 6}Entrada: arr[] = {6, 12, 18, 24}
Salida: 6
Enfoque ingenuo: el enfoque más simple para resolver este problema es generar todas las subsecuencias posibles de la array dada y calcular el GCD de cada subsecuencia. Imprime la subsecuencia más pequeña que tenga gcd igual a gcd de la array dada.
Complejidad de tiempo: O(2 N * N * log X), donde X es el elemento máximo de la array dada.
Espacio Auxiliar: O(1)
Enfoque eficiente: Para optimizar el enfoque anterior, la idea se basa en las siguientes observaciones:
La longitud de la subsecuencia más pequeña que tiene gcd igual a gcd de la array dada debe ser 1 o 2.
Considere, mcd de la array dada es Y .
Si arr[idx] = Y , entonces la longitud de la subsecuencia más pequeña debe ser 1 para algún valor de idx .
De lo contrario, la longitud de la subsecuencia más pequeña debe ser 2 .
Demostración usando el método de contradicción:
si gcd de todos los pares posibles de la array dada es mayor que Y , entonces gcd de la array dada debe ser mayor que Y , lo cual no es posible. Por lo tanto ,
existe al menos un par en la array dada cuyo mcd es igual a Y.
Siga los pasos a continuación para resolver el problema:
- Inicialice una variable gcdArr para almacenar GCD de la array .
- Recorra la array dada y verifique si algún elemento de la array es igual a gcdArr o no. Si se encuentra que es cierto, imprima ese elemento.
- De lo contrario, imprima un par de la array dada cuyo mcd sea igual a gcdArr .
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to print
// the smallest subsequence
// that satisfies the condition
void printSmallSub(int arr[], int N)
{
// Stores gcd of the array.
int gcdArr = 0;
// Traverse the given array
for (int i = 0; i < N; i++) {
// Update gcdArr
gcdArr = __gcd(gcdArr, arr[i]);
}
// Traverse the given array.
for (int i = 0; i < N; i++) {
// If current element
// equal to gcd of array.
if (arr[i] == gcdArr) {
cout << arr[i] << " ";
return;
}
}
// Generate all possible pairs.
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N;
j++) {
// If gcd of current pair
// equal to gcdArr
if (__gcd(arr[i], arr[j])
== gcdArr) {
// Print current pair
// of the array
cout << arr[i] << " " << arr[j];
return;
}
}
}
}
// Driver Code
int main()
{
int arr[] = { 4, 6, 12 };
int N = sizeof(arr) / sizeof(arr[0]);
printSmallSub(arr, N);
}
Java
// Java program to implement
// the above approach
import java.io.*;
class GFG{
// Function to calculate gcd
// of two numbers
static int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function to print
// the smallest subsequence
// that satisfies the condition
static void printSmallSub(int[] arr, int N)
{
// Stores gcd of the array.
int gcdArr = 0;
// Traverse the given array
for(int i = 0; i < N; i++)
{
// Update gcdArr
gcdArr = gcd(gcdArr, arr[i]);
}
// Traverse the given array.
for(int i = 0; i < N; i++)
{
// If current element
// equal to gcd of array.
if (arr[i] == gcdArr)
{
System.out.print(arr[i] + " ");
return;
}
}
// Generate all possible pairs.
for(int i = 0; i < N; i++)
{
for(int j = i + 1; j < N; j++)
{
// If gcd of current pair
// equal to gcdArr
if (gcd(arr[i], arr[j]) == gcdArr)
{
// Print current pair
// of the array
System.out.print(arr[i] + " " +
arr[j]);
return;
}
}
}
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 4, 6, 12 };
int N = arr.length;
printSmallSub(arr, N);
}
}
// This code is contributed by akhilsaini
Python3
# Python3 program to implement # the above approach import math # Function to print the # smallest subsequence # that satisfies the condition def printSmallSub(arr, N): # Stores gcd of the array. gcdArr = 0 # Traverse the given array for i in range(0, N): # Update gcdArr gcdArr = math.gcd(gcdArr, arr[i]) # Traverse the given array. for i in range(0, N): # If current element # equal to gcd of array. if (arr[i] == gcdArr): print(arr[i], end = " ") return # Generate all possible pairs. for i in range(0, N): for j in range(i + 1, N): # If gcd of current pair # equal to gcdArr if (math.gcd(arr[i], arr[j]) == gcdArr): # Print current pair # of the array print(arr[i], end = " ") print(arr[j], end = " ") return # Driver Code if __name__ == "__main__": arr = [ 4, 6, 12 ] N = len(arr) printSmallSub(arr, N) # This code is contributed by akhilsaini
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to calculate gcd
// of two numbers
static int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function to print the
// smallest subsequence
// that satisfies the condition
static void printSmallSub(int[] arr, int N)
{
// Stores gcd of the array.
int gcdArr = 0;
// Traverse the given array
for(int i = 0; i < N; i++)
{
// Update gcdArr
gcdArr = gcd(gcdArr, arr[i]);
}
// Traverse the given array.
for(int i = 0; i < N; i++)
{
// If current element
// equal to gcd of array.
if (arr[i] == gcdArr)
{
Console.Write(arr[i] + " ");
return;
}
}
// Generate all possible pairs.
for(int i = 0; i < N; i++)
{
for(int j = i + 1; j < N; j++)
{
// If gcd of current pair
// equal to gcdArr
if (gcd(arr[i], arr[j]) == gcdArr)
{
// Print current pair
// of the array
Console.Write(arr[i] + " " +
arr[j]);
return;
}
}
}
}
// Driver Code
public static void Main()
{
int[] arr = { 4, 6, 12 };
int N = arr.Length;
printSmallSub(arr, N);
}
}
// This code is contributed by akhilsaini
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to calculate gcd
// of two numbers
function gcd(a, b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function to print
// the smallest subsequence
// that satisfies the condition
function printSmallSub(arr, N)
{
// Stores gcd of the array.
let gcdArr = 0;
// Traverse the given array
for (let i = 0; i < N; i++) {
// Update gcdArr
gcdArr = gcd(gcdArr, arr[i]);
}
// Traverse the given array.
for (let i = 0; i < N; i++) {
// If current element
// equal to gcd of array.
if (arr[i] == gcdArr) {
document.write(arr[i] + " ");
return;
}
}
// Generate all possible pairs.
for (let i = 0; i < N; i++) {
for (let j = i + 1; j < N;
j++) {
// If gcd of current pair
// equal to gcdArr
if (gcd(arr[i], arr[j])
== gcdArr) {
// Print current pair
// of the array
document.write(arr[i] + " " + arr[j]);
return;
}
}
}
}
// Driver Code
let arr = [ 4, 6, 12 ];
let N = arr.length;
printSmallSub(arr, N);
// This is code is contributed by Mayank Tyagi
</script>
4 6
Complejidad de tiempo: (N 2 * log X), donde X es el elemento máximo de la array dada.
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por math_lover y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA