Dada una array arr[] que consta de N enteros positivos, la tarea es encontrar la longitud máxima de la subsecuencia de la array dada de modo que el GCD de dos enteros distintos cualquiera de la subsecuencia sea máximo .
Ejemplos:
Entrada: arr[] = {5, 14, 15, 20, 1}
Salida: 3
Explicación: La subsecuencia con MCD máximo de cualquier par de enteros distintos es {5, 15, 20}.
El GCD entre cualquier par de elementos distintos en la secuencia anterior es 5 y es el GCD máximo en la array.Entrada: arr[] = {1, 2, 8, 5, 6}
Salida: 3
Explicación: < La subsecuencia con MCD máximo de cualquier par de enteros distintos es {2, 8, 6}.
El GCD entre dos números distintos en la secuencia anterior es 2 y es el GCD máximo en la array.
Enfoque ingenuo: el enfoque más simple es usar la recursividad y generar recursivamente todas las subsecuencias posibles de la array dada y encontrar la longitud máxima entre esas subsecuencias. A continuación se muestran los pasos:
- Cree una función para encontrar el par en la array con máximo GCD (digamos maxGCD ) usando la idea de Sieve Of Eratosthenes .
- Cree otra función para contar la longitud máxima de la array de subsecuencias donde el GCD entre dos elementos distintos es máximo:
- Cree una array auxiliar arr1[] que almacene el elemento de array en orden ordenado .
- Inicialice las dos variables como [0, 0] y genere recursivamente toda la subsecuencia y devuelva la longitud máxima de la subsecuencia que tiene GCD como maxGCD .
- Después de los pasos anteriores, imprima la longitud máxima devuelta por las llamadas recursivas anteriores.
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 find GCD of pair with
// maximum GCD
int findMaxGCD(int arr[], int N)
{
// Stores maximum element of arr[]
int high = 0;
// Find the maximum element
for(int i = 0; i < N; i++)
{
high = max(high, arr[i]);
}
// Maintain a count array
int count[high + 1] = {0};
// Store the frequency of arr[]
for(int i = 0; i < N; i++)
{
count[arr[i]] += 1;
}
// Stores the multiples of a number
int counter = 0;
// Iterate over the range [MAX, 1]
for(int i = high; i > 0; i--)
{
int j = i;
// Iterate from current potential
// GCD till it is less than MAX
while (j <= high)
{
// A multiple found
if (count[j] > 0)
counter += count[j];
// Increment potential GCD by
// itself io check i, 2i, 3i...
j += i;
// If 2 multiples found max
// GCD found
if (counter == 2)
return i;
}
counter = 0;
}
}
// Function to find longest subsequence
// such that GCD of any two distinct
// integers is maximum
int maxlen(int i, int j, int arr[],
int arr1[], int N, int maxgcd)
{
int a = 1;
// Base Cases
if (i >= N or j >= N)
return 0;
// Compare current GCD to the
// maximum GCD
if (__gcd(arr[i], arr1[j]) == maxgcd &&
arr[i] != arr1[j])
{
// If true increment and
// move the pointer
a = max(a, 1 + maxlen(i, j + 1,
arr, arr1,
N, maxgcd));
return a;
}
// Return max of either subsequences
return max(maxlen(i + 1, j, arr,
arr1, N, maxgcd),
maxlen(i, j + 1, arr,
arr1, N, maxgcd));
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 8, 5, 6 };
int arr1[] = { 1, 2, 8, 5, 6 };
// Sorted array
int n = sizeof(arr) / sizeof(arr[0]);
sort(arr, arr + n);
sort(arr1, arr1 + n);
// Function call to calculate GCD of
// pair with maximum GCD
int maxgcd = findMaxGCD(arr, n);
// Print the result
cout << maxlen(0, 0, arr,
arr1, n, maxgcd) + 1;
}
// This code is contributed by ipg2016107
Java
// Java program for the
// above approach
import java.util.*;
class GFG{
// Recursive function to
// return gcd of a and b
static int __gcd(int a,
int b)
{
return b == 0 ?
a :__gcd(b, a % b);
}
// Function to find GCD of
// pair with maximum GCD
static int findMaxGCD(int arr[],
int N)
{
// Stores maximum element
// of arr[]
int high = 0;
// Find the maximum element
for(int i = 0; i < N; i++)
{
high = Math.max(high,
arr[i]);
}
// Maintain a count array
int []count = new int[high + 1];
// Store the frequency of arr[]
for(int i = 0; i < N; i++)
{
count[arr[i]] += 1;
}
// Stores the multiples of
// a number
int counter = 0;
// Iterate over the range
// [MAX, 1]
for(int i = high; i > 0; i--)
{
int j = i;
// Iterate from current potential
// GCD till it is less than MAX
while (j <= high)
{
// A multiple found
if (count[j] > 0)
counter += count[j];
// Increment potential GCD by
// itself io check i, 2i, 3i...
j += i;
// If 2 multiples found max
// GCD found
if (counter == 2)
return i;
}
counter = 0;
}
return 0;
}
// Function to find longest
// subsequence such that GCD
// of any two distinct integers
// is maximum
static int maxlen(int i, int j,
int arr[],
int arr1[],
int N, int maxgcd)
{
int a = 1;
// Base Cases
if (i >= N || j >= N)
return 0;
// Compare current GCD to
// the maximum GCD
if (__gcd(arr[i], arr1[j]) == maxgcd &&
arr[i] != arr1[j])
{
// If true increment and
// move the pointer
a = Math.max(a, 1 + maxlen(i, j + 1,
arr, arr1,
N, maxgcd));
return a;
}
// Return max of either subsequences
return Math.max(maxlen(i + 1, j, arr,
arr1, N, maxgcd),
maxlen(i, j + 1, arr,
arr1, N, maxgcd));
}
// Driver Code
public static void main(String[] args)
{
int arr[] = {1, 2, 8, 5, 6};
int arr1[] = {1, 2, 8, 5, 6};
// Sorted array
int n = arr.length;
Arrays.sort(arr);
// Function call to calculate GCD of
// pair with maximum GCD
int maxgcd = findMaxGCD(arr, n);
// Print the result
System.out.print(maxlen(0, 0, arr,
arr1, n, maxgcd));
}
}
// This code is contributed by gauravrajput1
Python3
# Python3 program for the above approach import math # Function to find GCD of pair with # maximum GCD def findMaxGCD(arr, N): # Stores maximum element of arr[] high = 0 # Find the maximum element for i in range(0, N): high = max(high, arr[i]) # Maintain a count array count = [0] * (high + 1) # Store the frequency of arr[] for i in range(0, N): count[arr[i]] += 1 # Stores the multiples of a number counter = 0 # Iterate over the range [MAX, 1] for i in range(high, 0, -1): j = i # Iterate from current potential # GCD till it is less than MAX while (j <= high): # A multiple found if (count[j] > 0): counter += count[j] # Increment potential GCD by # itself io check i, 2i, 3i... j += i # If 2 multiples found max # GCD found if (counter == 2): return i counter = 0 # Function to find longest subsequence # such that GCD of any two distinct # integers is maximum def maxlen(i, j): a = 0 # Base Cases if i >= N or j >= N: return 0 # Compare current GCD to the # maximum GCD if math.gcd(arr[i], arr1[j]) == maxgcd and arr[i] != arr1[j]: # If true increment and # move the pointer a = max(a, 1 + maxlen(i, j + 1)) return a # Return max of either subsequences return max(maxlen(i + 1, j), maxlen(i, j + 1)) # Drivers Code arr = [1, 2, 8, 5, 6] # Sorted array arr1 = sorted(arr) # Length of the array N = len(arr) # Function call to calculate GCD of # pair with maximum GCD maxgcd = findMaxGCD(arr, N) # Print the result print(maxlen(0, 0))
C#
// C# program for the
// above approach
using System;
class GFG{
// Recursive function to
// return gcd of a and b
static int __gcd(int a, int b)
{
return b == 0 ?
a :__gcd(b, a % b);
}
// Function to find GCD of
// pair with maximum GCD
static int findMaxGCD(int []arr,
int N)
{
// Stores maximum element
// of []arr
int high = 0;
// Find the maximum element
for(int i = 0; i < N; i++)
{
high = Math.Max(high,
arr[i]);
}
// Maintain a count array
int []count = new int[high + 1];
// Store the frequency of []arr
for(int i = 0; i < N; i++)
{
count[arr[i]] += 1;
}
// Stores the multiples of
// a number
int counter = 0;
// Iterate over the range
// [MAX, 1]
for(int i = high; i > 0; i--)
{
int j = i;
// Iterate from current potential
// GCD till it is less than MAX
while (j <= high)
{
// A multiple found
if (count[j] > 0)
counter += count[j];
// Increment potential GCD by
// itself io check i, 2i, 3i...
j += i;
// If 2 multiples found max
// GCD found
if (counter == 2)
return i;
}
counter = 0;
}
return 0;
}
// Function to find longest
// subsequence such that GCD
// of any two distinct integers
// is maximum
static int maxlen(int i, int j,
int []arr,
int []arr1,
int N, int maxgcd)
{
int a = 1;
// Base Cases
if (i >= N || j >= N)
return 0;
// Compare current GCD to
// the maximum GCD
if (__gcd(arr[i], arr1[j]) == maxgcd &&
arr[i] != arr1[j])
{
// If true increment and
// move the pointer
a = Math.Max(a, 1 + maxlen(i, j + 1,
arr, arr1,
N, maxgcd));
return a;
}
// Return max of either subsequences
return Math.Max(maxlen(i + 1, j, arr,
arr1, N, maxgcd),
maxlen(i, j + 1, arr,
arr1, N, maxgcd));
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 1, 2, 8, 5, 6 };
int []arr1 = { 1, 2, 8, 5, 6 };
// Sorted array
int n = arr.Length;
Array.Sort(arr);
// Function call to calculate GCD of
// pair with maximum GCD
int maxgcd = findMaxGCD(arr, n);
// Print the result
Console.Write(maxlen(0, 0, arr,
arr1, n, maxgcd));
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// javascript program for the
// above approach
// Recursive function to
// return gcd of a and b
function __gcd(a , b) {
return b == 0 ? a : __gcd(b, a % b);
}
// Function to find GCD of
// pair with maximum GCD
function findMaxGCD(arr, N)
{
// Stores maximum element
// of arr
var high = 0;
// Find the maximum element
for (i = 0; i < N; i++)
{
high = Math.max(high, arr[i]);
}
// Maintain a count array
var count = Array(high + 1).fill(0);
// Store the frequency of arr
for (i = 0; i < N; i++)
{
count[arr[i]] += 1;
}
// Stores the multiples of
// a number
var counter = 0;
// Iterate over the range
// [MAX, 1]
for (i = high; i > 0; i--)
{
var j = i;
// Iterate from current potential
// GCD till it is less than MAX
while (j <= high)
{
// A multiple found
if (count[j] > 0)
counter += count[j];
// Increment potential GCD by
// itself io check i, 2i, 3i...
j += i;
// If 2 multiples found max
// GCD found
if (counter == 2)
return i;
}
counter = 0;
}
return 0;
}
// Function to find longest
// subsequence such that GCD
// of any two distinct integers
// is maximum
function maxlen(i , j , arr , arr1 , N , maxgcd)
{
var a = 1;
// Base Cases
if (i >= N || j >= N)
return 0;
// Compare current GCD to
// the maximum GCD
if (__gcd(arr[i], arr1[j]) == maxgcd && arr[i] != arr1[j])
{
// If true increment and
// move the pointer
a = Math.max(a, 1 + maxlen(i, j + 1, arr, arr1, N, maxgcd));
return a;
}
// Return max of either subsequences
return Math.max(maxlen(i + 1, j, arr, arr1, N, maxgcd), maxlen(i, j + 1, arr, arr1, N, maxgcd));
}
// Driver Code
var arr = [ 1, 2, 8, 5, 6 ];
var arr1 = [ 1, 2, 8, 5, 6 ];
// Sorted array
var n = arr.length;
arr.sort();
// Function call to calculate GCD of
// pair with maximum GCD
var maxgcd = findMaxGCD(arr, n);
// Print the result
document.write(maxlen(0, 0, arr, arr1, n, maxgcd));
// This code is contributed by gauravrajput1.
</script>
Producción:
3
Complejidad temporal: O(2 N )
Espacio auxiliar: O(N)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar la programación dinámica , ya que hay muchos subproblemas superpuestos en la solución anterior que se resuelven una y otra vez. Por lo tanto, el recálculo de los mismos subproblemas se puede evitar usando Memoización o Tabulación . Use un diccionario para memorizar la longitud máxima de la subsecuencia entre dos índices y use esos valores en las próximas llamadas de recurrencia. A continuación se muestran los pasos:
- Realice todos los pasos explicados anteriormente.
- Use un diccionario dp para almacenar la longitud máxima de la subsecuencia entre dos índices.
- Mientras tiene la llamada recursiva, simplemente verifique en la tabla dp[][] si el valor se calculó previamente o no. Si se determina que es cierto , utilice este valor. De lo contrario, llame a la función para otro rango de índice.
- Imprime la longitud máxima de la subsecuencia calculada después de los pasos anteriores.
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;
map<pair<int, int>, int>dp;
int maxgcd;
vector<int>arr, arr1;
int N;
// Function to find GCD of pair with
// maximum GCD
int findMaxGCD(vector<int>arr, int N)
{
// Stores maximum element of arr[]
int high = 0;
// Find the maximum element
for(int i = 0; i < N; i++)
high = max(high, arr[i]);
// Maintain a count array
int count[high + 1] = {0};
// Store the frequency of arr[]
for(int i = 0; i < N; i++)
count[arr[i]] += 1;
// Stores the multiples of a number
int counter = 0;
// Iterate over the range [MAX, 1]
for(int i = high; i > 0; i--)
{
int j = i;
// Iterate from current potential
// GCD till it is less than MAX
while (j <= high)
{
// A multiple found
if (count[j] > 0)
counter += count[j];
// Increment potential GCD by
// itself io check i, 2i, 3i...
j += i;
// If 2 multiples found max
// GCD found
if (counter == 2)
return i;
}
counter = 0;
}
return 1;
}
// Function to find longest subsequence
// such that GCD of any two distinct
// integers is maximum
int maxlen(int i, int j)
{
int a = 0;
// Create the key
// Base Case
if (i >= N or j >= N)
return 0;
// Check if the current state is
// already calculated
if (dp[{i, j}])
return dp[{i, j}];
// Compare current GCD to the
// maximum GCD
if (__gcd(arr[i], arr1[j]) ==
maxgcd && arr[i] != arr1[j])
{
// If true increment and
// move the pointer
dp[{i, j}] = 1 + maxlen(i, j + 1);
return dp[{i, j}];
}
// Return max of either subsequences
return (max(maxlen(i + 1, j),
maxlen(i, j + 1)));
}
// Driver Code
int main()
{
arr = { 1, 2, 8, 5, 6 };
arr1 = arr;
// Sorted array
sort(arr1.begin(), arr1.end());
// Length of the array
N = arr.size();
// Function Call
maxgcd = findMaxGCD(arr, N);
// Print the result
cout << (maxlen(0, 0));
}
// This code is contributed by Stream_Cipher
Java
// Java program for the above approach
import java.util.*;
import java.awt.Point;
public class Main
{
static HashMap<Point, Integer> dp = new HashMap<>();
static int maxgcd, N;
static Vector<Integer> arr;
static Vector<Integer> arr1;
static int __gcd(int a, int b)
{
if (b == 0)
return a;
return __gcd(b, a % b);
}
// Function to find GCD of pair with
// maximum GCD
static int findMaxGCD(Vector<Integer> arr, int N)
{
// Stores maximum element of arr[]
int high = 0;
// Find the maximum element
for(int i = 0; i < N; i++)
high = Math.max(high, arr.get(i));
// Maintain a count array
int[] count = new int[high + 1];
// Store the frequency of arr[]
for(int i = 0; i < N; i++)
count[arr.get(i)] += 1;
// Stores the multiples of a number
int counter = 0;
// Iterate over the range [MAX, 1]
for(int i = high; i > 0; i--)
{
int j = i;
// Iterate from current potential
// GCD till it is less than MAX
while (j <= high)
{
// A multiple found
if (count[j] > 0)
counter += count[j];
// Increment potential GCD by
// itself io check i, 2i, 3i...
j += i;
// If 2 multiples found max
// GCD found
if (counter == 2)
return i;
}
counter = 0;
}
return 1;
}
// Function to find longest subsequence
// such that GCD of any two distinct
// integers is maximum
static int maxlen(int i, int j)
{
// Create the key
// Base Case
if (i >= N || j >= N)
return 0;
// Check if the current state is
// already calculated
if (dp.containsKey(new Point(i, j)))
return dp.get(new Point(i, j));
// Compare current GCD to the
// maximum GCD
if (__gcd(arr.get(i), arr1.get(j)) ==
maxgcd && arr.get(i) != arr1.get(j))
{
// If true increment and
// move the pointer
dp.put(new Point(i, j), 1 + maxlen(i, j + 1));
return dp.get(new Point(i, j));
}
// Return max of either subsequences
return (Math.max(maxlen(i + 1, j), maxlen(i, j + 1)));
}
public static void main(String[] args) {
arr = new Vector<Integer>();
arr.add(1);
arr.add(2);
arr.add(8);
arr.add(5);
arr.add(6);
arr1 = arr;
// Sorted array
Collections.sort(arr1);
// Length of the array
N = arr.size();
// Function Call
maxgcd = findMaxGCD(arr, N);
// Print the result
System.out.println(maxlen(0, 0) + 1);
}
}
// This code is contributed by divyeshrabadiya07.
Python3
# Python3 program for the above approach import math # Function to find GCD of pair with # maximum GCD def findMaxGCD(arr, N): # Stores maximum element of arr[] high = 0 # Find the maximum element for i in range(0, N): high = max(high, arr[i]) # Maintain a count array count = [0] * (high + 1) # Store the frequency of arr[] for i in range(0, N): count[arr[i]] += 1 # Stores the multiples of a number counter = 0 # Iterate over the range [MAX, 1] for i in range(high, 0, -1): j = i # Iterate from current potential # GCD till it is less than MAX while (j <= high): # A multiple found if (count[j] > 0): counter += count[j] # Increment potential GCD by # itself io check i, 2i, 3i... j += i # If 2 multiples found max # GCD found if (counter == 2): return i counter = 0 # Function to find longest subsequence # such that GCD of any two distinct # integers is maximum def maxlen(i, j): a = 0 # Create the key key = (i, j) # Base Case if i >= N or j >= N: return 0 # Check if the current state is # already calculated if key in dp: return dp[key] # Compare current GCD to the # maximum GCD if math.gcd(arr[i], arr1[j]) == maxgcd and arr[i] != arr1[j]: # If true increment and # move the pointer dp[key] = 1 + maxlen(i, j + 1) return dp[key] # Return max of either subsequences return max(maxlen(i + 1, j), maxlen(i, j + 1)) # Drivers code arr = [1, 2, 8, 5, 6] # Empty dictionary dp = dict() # Sorted array arr1 = sorted(arr) # Length of the array N = len(arr) # Function Call maxgcd = findMaxGCD(arr, N) # Print the result print(maxlen(0, 0))
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
static Dictionary<Tuple<int,
int>, int> dp = new Dictionary<Tuple<int,
int>, int>();
static int maxgcd, N;
static List<int> arr;
static List<int> arr1;
static int __gcd(int a, int b)
{
if (b == 0)
return a;
return __gcd(b, a % b);
}
// Function to find GCD of pair with
// maximum GCD
static int findMaxGCD(List<int> arr, int N)
{
// Stores maximum element of arr[]
int high = 0;
// Find the maximum element
for(int i = 0; i < N; i++)
high = Math.Max(high, arr[i]);
// Maintain a count array
int[] count = new int[high + 1];
// Store the frequency of arr[]
for(int i = 0; i < N; i++)
count[arr[i]] += 1;
// Stores the multiples of a number
int counter = 0;
// Iterate over the range [MAX, 1]
for(int i = high; i > 0; i--)
{
int j = i;
// Iterate from current potential
// GCD till it is less than MAX
while (j <= high)
{
// A multiple found
if (count[j] > 0)
counter += count[j];
// Increment potential GCD by
// itself io check i, 2i, 3i...
j += i;
// If 2 multiples found max
// GCD found
if (counter == 2)
return i;
}
counter = 0;
}
return 1;
}
// Function to find longest subsequence
// such that GCD of any two distinct
// integers is maximum
static int maxlen(int i, int j)
{
// Create the key
// Base Case
if (i >= N || j >= N)
return 0;
// Check if the current state is
// already calculated
if (dp.ContainsKey(new Tuple<int, int>(i, j)))
return dp[new Tuple<int, int>(i, j)];
// Compare current GCD to the
// maximum GCD
if (__gcd(arr[i], arr1[j]) ==
maxgcd && arr[i] != arr1[j])
{
// If true increment and
// move the pointer
dp[new Tuple<int, int>(i, j)] = 1 + maxlen(
i, j + 1);
return dp[new Tuple<int, int>(i, j)];
}
// Return max of either subsequences
return (Math.Max(maxlen(i + 1, j),
maxlen(i, j + 1)));
}
// Driver code
static void Main()
{
arr = new List<int>(new int[]{ 1, 2, 8, 5, 6 });
arr1 = arr;
// Sorted array
arr1.Sort();
// Length of the array
N = arr.Count;
// Function Call
maxgcd = findMaxGCD(arr, N);
// Print the result
Console.Write(maxlen(0, 0) + 1);
}
}
// This code is contributed by divyesh072019
Javascript
<script>
// JavaScript program for the above approach
var dp = new Map();
var maxgcd;
var arr = [], arr1 = [];
var N;
// Function to find GCD of pair with
// maximum GCD
function findMaxGCD(arr, N)
{
// Stores maximum element of arr[]
var high = 0;
// Find the maximum element
for(var i = 0; i < N; i++)
high = Math.max(high, arr[i]);
// Maintain a count array
var count = Array(high+1).fill(0);
// Store the frequency of arr[]
for(var i = 0; i < N; i++)
count[arr[i]] += 1;
// Stores the multiples of a number
var counter = 0;
// Iterate over the range [MAX, 1]
for(var i = high; i > 0; i--)
{
var j = i;
// Iterate from current potential
// GCD till it is less than MAX
while (j <= high)
{
// A multiple found
if (count[j] > 0)
counter += count[j];
// Increment potential GCD by
// itself io check i, 2i, 3i...
j += i;
// If 2 multiples found max
// GCD found
if (counter == 2)
return i;
}
counter = 0;
}
return 1;
}
function __gcd(a, b)
{
if (b == 0)
return a;
return __gcd(b, a % b);
}
// Function to find longest subsequence
// such that GCD of any two distinct
// integers is maximum
function maxlen(i, j)
{
var a = 0;
// Create the key
// Base Case
if (i >= N || j >= N)
return 0;
// Check if the current state is
// already calculated
if (dp.has([i, j].toString()))
return dp.get([i, j].toString());
// Compare current GCD to the
// maximum GCD
if (__gcd(arr[i], arr1[j]) ==
maxgcd && arr[i] != arr1[j])
{
// If true increment and
// move the pointer
dp.set([i, j].toString(), 1 + maxlen(i, j + 1));
return dp.get([i, j].toString());
}
// Return max of either subsequences
return (Math.max(maxlen(i + 1, j),
maxlen(i, j + 1)));
}
// Driver Code
arr = [1, 2, 8, 5, 6];
arr1 = JSON.parse(JSON.stringify(arr));
// Sorted array
arr1.sort((a,b)=>a-b);
// Length of the array
N = arr.length;
// Function Call
maxgcd = findMaxGCD(arr, N);
// Print the result
document.write(maxlen(0, 0));
</script>
Producción:
3
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por saikumarkudikala y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA