Dado un arr[] , la tarea es encontrar la longitud máxima del subconjunto tal que el MCM del subconjunto sea igual al producto de los números del subconjunto. Si no existe un subarreglo válido, imprima -1 .
Nota: La longitud del subarreglo debe ser ≥ 2.
Ejemplos:
Entrada: array[] = { 6, 10, 21}
Salida: 2
La sub-array { 10, 21 } satisface la condición.Entrada: arr[] = { 2, 2, 4}
Salida: -1
Ningún subarreglo cumple la condición. Por lo tanto, la salida es -1.
Enfoque ingenuo: Ejecute bucles anidados para comprobar la condición de cada subarreglo posible de longitud ≥ 2. Si el subarreglo cumple la condición, actualice ans = max(ans, length(sub-arreglo)) . Imprime el ans al final.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
#define ll long long
// Function to calculate gcd(a, b)
int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function to return max length of subarray
// that satisfies the condition
int maxLengthSubArray(const int* arr, int n)
{
int maxLen = -1;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
ll lcm = 1LL * arr[i];
ll product = 1LL * arr[i];
// Update LCM and product of the
// sub-array
for (int k = i + 1; k <= j; k++) {
lcm = (((arr[k] * lcm)) /
(gcd(arr[k], lcm)));
product = product * arr[k];
}
// If the current sub-array satisfies
// the condition
if (lcm == product) {
// Choose the maximum
maxLen = max(maxLen, j - i + 1);
}
}
}
return maxLen;
}
// Driver code
int main()
{
int arr[] = { 6, 10, 21 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << maxLengthSubArray(arr, n);
return 0;
}
Java
// Java implementation of the above approach
import java.util.*;
class GFG
{
// Function to calculate gcd(a, b)
static int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function to return max length of subarray
// that satisfies the condition
static int maxLengthSubArray(int arr[], int n)
{
int maxLen = -1;
for (int i = 0; i < n - 1; i++)
{
for (int j = i + 1; j < n; j++)
{
int lcm = 1 * arr[i];
int product = 1 * arr[i];
// Update LCM and product of the
// sub-array
for (int k = i + 1; k <= j; k++)
{
lcm = (((arr[k] * lcm)) /
(gcd(arr[k], lcm)));
product = product * arr[k];
}
// If the current sub-array satisfies
// the condition
if (lcm == product)
{
// Choose the maximum
maxLen = Math.max(maxLen, j - i + 1);
}
}
}
return maxLen;
}
// Driver code
public static void main(String args[])
{
int arr[] = { 6, 10, 21 };
int n = arr.length;
System.out.println(maxLengthSubArray(arr, n));
}
}
// This code is contributed by
// Shashank_Sharma
Python3
# Python3 implementation of the # above approach # Function to calculate gcd(a, b) def gcd(a, b): if (b == 0): return a return gcd(b, a % b) # Function to return max length of # subarray that satisfies the condition def maxLengthSubArray(arr, n): maxLen = -1 for i in range(n - 1): for j in range(n): lcm = arr[i] product = arr[i] # Update LCM and product of the # sub-array for k in range(i + 1, j + 1): lcm = (((arr[k] * lcm)) // (gcd(arr[k], lcm))) product = product * arr[k] # If the current sub-array satisfies # the condition if (lcm == product): # Choose the maximum maxLen = max(maxLen, j - i + 1) return maxLen # Driver code arr = [6, 10, 21 ] n = len(arr) print(maxLengthSubArray(arr, n)) # This code is contributed by # mohit kumar 29
C#
// C# implementation of the above approach
using System;
class GFG
{
// Function to calculate gcd(a, b)
static int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function to return max length of subarray
// that satisfies the condition
static int maxLengthSubArray(int[] arr, int n)
{
int maxLen = -1;
for (int i = 0; i < n - 1; i++)
{
for (int j = i + 1; j < n; j++)
{
int lcm = 1 * arr[i];
int product = 1 * arr[i];
// Update LCM and product of the
// sub-array
for (int k = i + 1; k <= j; k++)
{
lcm = (((arr[k] * lcm)) /
(gcd(arr[k], lcm)));
product = product * arr[k];
}
// If the current sub-array satisfies
// the condition
if (lcm == product)
{
// Choose the maximum
maxLen = Math.Max(maxLen, j - i + 1);
}
}
}
return maxLen;
}
// Driver code
public static void Main()
{
int[] arr = { 6, 10, 21 };
int n = arr.Length;
Console.Write(maxLengthSubArray(arr, n));
}
}
// This code is contributed by ita_c
PHP
<?php
// PHP implementation of the above approach
// Function to calculate gcd(a, b)
function gcd($a, $b)
{
if ($b == 0)
return $a;
return gcd($b, $a % $b);
}
// Function to return max length of subarray
// that satisfies the condition
function maxLengthSubArray(&$arr, $n)
{
$maxLen = -1;
for ($i = 0; $i < $n - 1; $i++)
{
for ($j = $i + 1; $j < $n; $j++)
{
$lcm = $arr[$i];
$product = $arr[$i];
// Update LCM and product of the
// sub-array
for ($k = $i + 1; $k <= $j; $k++)
{
$lcm = ((($arr[$k] * $lcm)) /
(gcd($arr[$k], $lcm)));
$product = $product * $arr[$k];
}
// If the current sub-array satisfies
// the condition
if ($lcm == $product)
{
// Choose the maximum
$maxLen = max($maxLen, $j - $i + 1);
}
}
}
return $maxLen;
}
// Driver code
$arr = array(6, 10, 21 );
$n = sizeof($arr);
echo(maxLengthSubArray($arr, $n));
// This code is contributed by Shivi_Aggarwal
?>
Javascript
<script>
// Javascript implementation of the above approach
// Function to calculate gcd(a, b)
function gcd(a,b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function to return max length of subarray
// that satisfies the condition
function maxLengthSubArray(arr,n)
{
let maxLen = -1;
for (let i = 0; i < n - 1; i++)
{
for (let j = i + 1; j < n; j++)
{
let lcm = 1 * arr[i];
let product = 1 * arr[i];
// Update LCM and product of the
// sub-array
for (let k = i + 1; k <= j; k++)
{
lcm = (((arr[k] * lcm)) /
(gcd(arr[k], lcm)));
product = product * arr[k];
}
// If the current sub-array satisfies
// the condition
if (lcm == product)
{
// Choose the maximum
maxLen = Math.max(maxLen, j - i + 1);
}
}
}
return maxLen;
}
// Driver code
let arr=[6, 10, 21 ];
let n = arr.length;
document.write(maxLengthSubArray(arr, n));
// This code is contributed by unknown2108
</script>
Producción:
2
Enfoque eficiente: un subarreglo tendrá su MCM igual a su producto cuando no haya dos elementos en el subarreglo que tengan un factor común.
Por ejemplo:
arr[] = { 6, 10, 21 } La
factorización prima produce:
arr[] = { 2 * 3, 2 * 5, 3 * 7 }
[6, 10] tiene 2 como factor común.
[6, 10, 21] tiene 2 como factor común entre 6 y 10.
El subconjunto [10, 21] no tiene factor común entre 2 elementos. Por lo tanto, respuesta = 2.
En primer lugar, la descomposición en factores primos de números se realiza para tratar con factores. Para calcular el subarreglo en el que no hay 2 elementos que tengan un factor común, usamos la técnica de dos punteros.
Se ejecutan dos punteros, ambos desde la derecha y representan el subarreglo actual. Agregamos elementos en la sub-array desde la derecha. Ahora hay dos escenarios:
- Se agrega un elemento en el subconjunto actual si no tiene ningún factor en común con los elementos actuales del subconjunto. Si se encuentra un factor común, entonces comenzando desde la izquierda, los elementos se eliminan posteriormente hasta que no se encuentre ningún factor común con el elemento recién agregado.
- Si no hay factores comunes entre el elemento recién agregado y los elementos existentes, entonces actualice ans = max(ans, longitud del subarreglo)
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
#define pb push_back
#define N 100005
#define MAX 1000002
#define mem(a, b) memset(a, b, sizeof(a))
using namespace std;
int prime[MAX];
// Stores array of primes for every element
vector<int> v[N];
// Stores the position of a prime in the subarray
// in two pointer technique
int f[MAX];
// Function to store smallest prime factor of numbers
void sieve()
{
prime[0] = prime[1] = 1;
for (int i = 2; i < MAX; i++) {
if (!prime[i]) {
for (int j = i * 2; j < MAX; j += i) {
if (!prime[j])
prime[j] = i;
}
}
}
for (int i = 2; i < MAX; i++) {
// If number is prime,
// then smallest prime factor is the
// number itself
if (!prime[i])
prime[i] = i;
}
}
// Function to return maximum length of subarray
// with LCM = product
int maxLengthSubArray(int* arr, int n)
{
// Initialize f with -1
mem(f, -1);
for (int i = 0; i < n; ++i) {
// Prime factorization of numbers
// Store primes in a vector for every element
while (arr[i] > 1) {
int p = prime[arr[i]];
arr[i] /= p;
v[i].pb(p);
}
}
// Two pointers l and r
// denoting left and right of subarray
int l = 0, r = 1, ans = -1;
// f is a mapping.
// prime -> index in the current subarray
// With the help of f,
// we can detect whether a prime has
// already occurred in the subarray
for (int i : v[0]) {
f[i] = 0;
}
while (l <= r && r < n) {
int flag = 0;
for (int i = 0; i < v[r].size(); i++) {
// Map the prime to the index
if (f[v[r][i]] == -1 || f[v[r][i]] == r) {
f[v[r][i]] = r;
}
// If already occurred then,
// start removing elements from the left
else {
flag = 1;
break;
}
}
// Remove elements if flag = 1
if (flag) {
// Nullify entries of element at index 'l'
for (int i : v[l]) {
f[i] = -1;
}
// Increment 'l'
l++;
}
else {
// Maximize the answer when
// no common factor is found
ans = max(ans, r - l + 1);
r++;
}
}
// One length subarray is discarded
if (ans == 1)
ans = -1;
return ans;
}
// Driver code
int main()
{
sieve();
int arr[] = { 6, 10, 21 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << maxLengthSubArray(arr, n);
return 0;
}
Java
// Java implementation of the above approach
import java.io.*;
import java.util.*;
class GFG{
static int N = 100005;
static int MAX = 1000002;
static int[] prime = new int[MAX];
// Stores array of primes for every element
static ArrayList<
ArrayList<Integer>> v = new ArrayList<
ArrayList<Integer>>();
// Stores the position of a prime in the
// subarray in two pointer technique
static int[] f = new int[MAX];
// Function to store smallest prime
// factor of numbers
static void sieve()
{
for(int i = 0; i < N; i++)
{
v.add(new ArrayList<Integer>());
}
prime[0] = prime[1] = 1;
for(int i = 2; i < MAX; i++)
{
if (prime[i] == 0)
{
for(int j = i * 2; j < MAX; j += i)
{
if (prime[j] == 0)
{
prime[j] = i;
}
}
}
}
for(int i = 2; i < MAX; i++)
{
// If number is prime, then
// smallest prime factor is
// the number itself
if (prime[i] == 0)
{
prime[i] = i;
}
}
}
// Function to return maximum length of
// subarray with LCM = product
static int maxLengthSubArray(int[] arr, int n)
{
// Initialize f with -1
Arrays.fill(f, -1);
for(int i = 0; i < n; ++i)
{
// Prime factorization of numbers
// Store primes in a vector for
// every element
while (arr[i] > 1)
{
int p = prime[arr[i]];
arr[i] /= p;
v.get(i).add(p);
}
}
// Two pointers l and r denoting
// left and right of subarray
int l = 0, r = 1, ans = -1;
// f is a mapping.
// prime -> index in the current subarray
// With the help of f,
// we can detect whether a prime has
// already occurred in the subarray
for(int i : v.get(0))
{
f[i] = 0;
}
while (l <= r && r < n)
{
int flag = 0;
for(int i = 0; i < v.get(r).size(); i++)
{
// Map the prime to the index
if (f[v.get(r).get(i)] == -1 ||
f[v.get(r).get(i)] == r)
{
f[v.get(r).get(i)] = r;
}
// If already occurred then,
// start removing elements
// from the left
else
{
flag = 1;
break;
}
}
// Remove elements if flag = 1
if (flag != 0)
{
// Nullify entries of element
// at index 'l'
for(int i : v.get(l))
{
f[i] = -1;
}
// Increment 'l'
l++;
}
else
{
// Maximize the answer when
// no common factor is found
ans = Math.max(ans, r - l + 1);
r++;
}
}
// One length subarray is discarded
if (ans == 1)
{
ans = -1;
}
return ans;
}
// Driver code
public static void main(String[] args)
{
sieve();
int arr[] = { 6, 10, 21 };
int n = arr.length;
System.out.println(maxLengthSubArray(arr, n));
}
}
// This code is contributed by avanitrachhadiya2155
Python3
# Python3 implementation of the above approach N = 100005 MAX = 1000002 prime = [0 for i in range(MAX + 1)] # Stores array of primes for every element v = [[] for i in range(N)] # Stores the position of a prime in the subarray # in two pointer technique f = [-1 for i in range(MAX)] # Function to store smallest prime factor of numbers def sieve(): prime[0], prime[1] = 1, 1 for i in range(2, MAX + 1): if (prime[i] == 0): for j in range(i * 2, MAX, i): if (prime[j] == 0): prime[j] = i for i in range(2, MAX): # If number is prime, # then smallest prime factor is the # number itself if (prime[i] == 0): prime[i] = i # Function to return maximum length of subarray # with LCM = product def maxLengthSubArray(arr, n): # Initialize f with -1 for i in range(n): f[i] = -1 for i in range(n): # Prime factorization of numbers # Store primes in a vector for every element while (arr[i] > 1): p = prime[arr[i]] arr[i] //= p v[i].append(p) # Two pointers l and r # denoting left and right of subarray l, r, ans = 0, 1, -1 # f is a mapping. # prime -> index in the current subarray # With the help of f, # we can detect whether a prime has # already occurred in the subarray for i in v[0]: f[i] = 0 while (l <= r and r < n): flag = 0 for i in range(len(v[r])): # Map the prime to the index if (f[v[r][i]] == -1 or f[v[r][i]] == r): f[v[r][i]] = r # If already occurred then, # start removing elements from the left else: flag = 1 break # Remove elements if flag = 1 if (flag): # Nullify entries of element at index 'l' for i in v[l]: f[i] = -1 # Increment 'l' l += 1 else : # Maximize the answer when # no common factor is found ans = max(ans, r - l + 1) r += 1 # One length subarray is discarded if (ans == 1): ans = -1 return ans # Driver code sieve() arr = [6, 10, 21] n = len(arr) print(maxLengthSubArray(arr, n)) # This code is contributed by mohit kumar
C#
// C# implementation of the above approach
using System;
using System.Collections.Generic;
class GFG
{
static int N = 100005;
static int MAX = 1000002;
static int[] prime = new int[MAX];
// Stores array of primes for every element
static List<List<int>> v = new List<List<int>>();
// Stores the position of a prime in the
// subarray in two pointer technique
static int[] f = new int[MAX];
// Function to store smallest prime
// factor of numbers
static void sieve()
{
for(int i = 0; i < N; i++)
{
v.Add(new List<int>());
}
prime[0] = prime[1] = 1;
for(int i = 2; i < MAX; i++)
{
if (prime[i] == 0)
{
for(int j = i * 2; j < MAX; j += i)
{
if (prime[j] == 0)
{
prime[j] = i;
}
}
}
}
for(int i = 2; i < MAX; i++)
{
// If number is prime, then
// smallest prime factor is
// the number itself
if (prime[i] == 0)
{
prime[i] = i;
}
}
}
// Function to return maximum length of
// subarray with LCM = product
static int maxLengthSubArray(int[] arr, int n)
{
// Initialize f with -1
Array.Fill(f, -1);
for(int i = 0; i < n; ++i)
{
// Prime factorization of numbers
// Store primes in a vector for
// every element
while (arr[i] > 1)
{
int p = prime[arr[i]];
arr[i] /= p;
v[i].Add(p);
}
}
// Two pointers l and r denoting
// left and right of subarray
int l = 0, r = 1, ans = -1;
// f is a mapping.
// prime -> index in the current subarray
// With the help of f,
// we can detect whether a prime has
// already occurred in the subarray
foreach(int i in v[0])
{
f[i] = 0;
}
while (l <= r && r < n)
{
int flag = 0;
for(int i = 0; i < v[r].Count; i++)
{
// Map the prime to the index
if (f[v[r][i]] == -1 ||
f[v[r][i]] == r)
{
f[v[r][i]] = r;
}
// If already occurred then,
// start removing elements
// from the left
else
{
flag = 1;
break;
}
}
// Remove elements if flag = 1
if (flag != 0)
{
// Nullify entries of element
// at index 'l'
foreach(int i in v[l])
{
f[i] = -1;
}
// Increment 'l'
l++;
}
else
{
// Maximize the answer when
// no common factor is found
ans = Math.Max(ans, r - l + 1);
r++;
}
}
// One length subarray is discarded
if (ans == 1)
{
ans = -1;
}
return ans;
}
// Driver code
static public void Main ()
{
sieve();
int[] arr = { 6, 10, 21 };
int n = arr.Length;
Console.WriteLine(maxLengthSubArray(arr, n));
}
}
// This code is contributed by rag2127
Javascript
<script>
// Javascript implementation of the above approach
let N = 100005;
let MAX = 1000002;
let prime = new Array(MAX);
for(let i=0;i<prime.length;i++)
{
prime[i]=0;
}
// Stores array of primes for every element
let v = [];
// Stores the position of a prime in the
// subarray in two pointer technique
let f = new Array(MAX);
// Function to store smallest prime
// factor of numbers
function sieve()
{
for(let i = 0; i < N; i++)
{
v.push([]);
}
prime[0] = prime[1] = 1;
for(let i = 2; i < MAX; i++)
{
if (prime[i] == 0)
{
for(let j = i * 2; j < MAX; j += i)
{
if (prime[j] == 0)
{
prime[j] = i;
}
}
}
}
for(let i = 2; i < MAX; i++)
{
// If number is prime, then
// smallest prime factor is
// the number itself
if (prime[i] == 0)
{
prime[i] = i;
}
}
}
// Function to return maximum length of
// subarray with LCM = product
function maxLengthSubArray(arr,n)
{
// Initialize f with -1
for(let i=0;i<f.length;i++)
{
f[i]=-1;
}
for(let i = 0; i < n; ++i)
{
// Prime factorization of numbers
// Store primes in a vector for
// every element
while (arr[i] > 1)
{
let p = prime[arr[i]];
arr[i] /= p;
v[i].push(p);
}
}
// Two pointers l and r denoting
// left and right of subarray
let l = 0, r = 1, ans = -1;
// f is a mapping.
// prime -> index in the current subarray
// With the help of f,
// we can detect whether a prime has
// already occurred in the subarray
for(let i=0;i< v[0].length;i++)
{
f[v[0][i]] = 0;
}
while (l <= r && r < n)
{
let flag = 0;
for(let i = 0; i < v[r].length; i++)
{
// Map the prime to the index
if (f[v[r][i]] == -1 ||
f[v[r][i]] == r)
{
f[v[r][i]] = r;
}
// If already occurred then,
// start removing elements
// from the left
else
{
flag = 1;
break;
}
}
// Remove elements if flag = 1
if (flag != 0)
{
// Nullify entries of element
// at index 'l'
for(let i=0;i<v[l].length;i++)
{
f[v[l][i]] = -1;
}
// Increment 'l'
l++;
}
else
{
// Maximize the answer when
// no common factor is found
ans = Math.max(ans, r - l + 1);
r++;
}
}
// One length subarray is discarded
if (ans == 1)
{
ans = -1;
}
return ans;
}
// Driver code
sieve();
let arr=[ 6, 10, 21];
let n = arr.length;
document.write(maxLengthSubArray(arr, n));
// This code is contributed by patel2127
</script>
Producción:
2
Publicación traducida automáticamente
Artículo escrito por rohan23chhabra y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA