Hay una array con n elementos. Encuentre la longitud del subarreglo más grande que tiene GCD igual a 1. Si no hay subarreglo con GCD 1, imprima -1.
Ejemplos:
Input : 1 3 5 Output : 3 Input : 2 4 6 Output :-1
Una solución simple es considerar cada subarreglo y encontrar su GCD y realizar un seguimiento del subarreglo más grande con GCD uno. Finalmente, devuelva la longitud del subarreglo más grande con GCD 1.
Una solución eficiente se basa en el hecho de que si dos elementos tienen GCD igual a uno, entonces toda la array tiene GCD uno. Entonces, la salida es -1 o la longitud de la array.
C++
// C++ program, to find length of the largest
// subarray with GCD equals to 1.
#include<bits/stdc++.h>
using namespace std;
int findLargest(int arr[], int n)
{
/*If gcd of any subarray is 1 then gcd of
any number with the sub array will be 1.
so if we are getting any subarray with
gcd 1, then maximum number of element of
the subarray will be equal to the number
of elements of the array. Else it will be -1.*/
int gcd = arr[0];
for (int i=1; i<n; i++)
gcd = __gcd(gcd, arr[i]);
return (gcd == 1)? n : -1;
}
// Driver code
int main()
{
int arr[] = {1, 3, 5, 7};
int n = sizeof(arr)/sizeof(int);
cout << "Length of the largest subarray = "
<< findLargest(arr, n);
return 0;
}
Java
// Java program, to find length of the
// largest subarray with GCD equals to 1.
class GFG {
static int ___gcd(int a, int b)
{
// Everything divides 0
if (a == 0 || b == 0)
return 0;
// base case
if (a == b)
return a;
// a is greater
if (a > b)
return ___gcd(a - b, b);
return ___gcd(a, b - a);
}
static int findLargest(int arr[],
int n)
{
/*If gcd of any subarray is 1
then gcd of any number with the
sub array will be 1. so if we
are getting any subarray with
gcd 1, then maximum number of
element of the subarray will
be equal to the number of
elements of the array. Else
it will be -1.*/
int gcd = arr[0];
for (int i = 1; i < n; i++)
gcd = ___gcd(gcd, arr[i]);
return (gcd == 1)? n : -1;
}
// Driver code
public static void main (String[] args)
{
int arr[] = {1, 3, 5, 7};
int n = arr.length;
System.out.print("Length of the "
+ "largest subarray = "
+ findLargest(arr, n));
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python program, to find
# length of the largest
# subarray with GCD equals to 1.
def ___gcd(a,b):
# Everything divides 0
if (a == 0 or b == 0):
return 0
# base case
if (a == b):
return a
# a is greater
if (a > b):
return ___gcd(a-b, b)
return ___gcd(a, b-a)
def findLargest(arr, n):
'''If gcd of any subarray is 1 then gcd of
any number with the sub array will be 1.
so if we are getting any subarray with
gcd 1, then maximum number of element of
the subarray will be equal to the number
of elements of the array. Else it will be -1.'''
gcd = arr[0]
for i in range(1,n):
gcd = ___gcd(gcd, arr[i])
return n if (gcd == 1) else -1
# Driver code
arr=[1, 3, 5, 7]
n=len(arr)
print("Length of the largest subarray = ",
findLargest(arr, n))
# This code is contributed
# by Anant Agarwal.
C#
// C# program, to find length of the
// largest subarray with GCD equals to 1.
using System;
class GFG {
static int ___gcd(int a, int b)
{
// Everything divides 0
if (a == 0 || b == 0)
return 0;
// base case
if (a == b)
return a;
// a is greater
if (a > b)
return ___gcd(a - b, b);
return ___gcd(a, b - a);
}
static int findLargest(int []arr,
int n)
{
// If gcd of any subarray is 1
// then gcd of any number with the
// sub array will be 1. so if we
// are getting any subarray with
// gcd 1, then maximum number of
// element of the subarray will
// be equal to the number of
// elements of the array. Else
// it will be -1.
int gcd = arr[0];
for (int i = 1; i < n; i++)
gcd = ___gcd(gcd, arr[i]);
return (gcd == 1)? n : -1;
}
// Driver code
public static void Main ()
{
int []arr = {1, 3, 5, 7};
int n = arr.Length;
Console.Write("Length of the "
+ "largest subarray = "
+ findLargest(arr, n));
}
}
// This code is contributed by Nitin Mittal.
PHP
<?php
// PHP program, to find length
// of the largest subarray with
// GCD equals to 1.
function ___gcd($a, $b)
{
// Everything divides 0
if ($a == 0 || $b == 0)
return 0;
// base case
if ($a == $b)
return $a;
// a is greater
if ($a > $b)
return ___gcd($a - $b, $b);
return ___gcd($a, $b - $a);
}
function findLargest($arr, $n)
{
/*If gcd of any subarray is 1
then gcd of any number with the
sub array will be 1. so if we
are getting any subarray with
gcd 1, then maximum number of
element of the subarray will
be equal to the number of
elements of the array. Else
it will be -1.*/
$gcd = $arr[0];
for ($i = 1; $i < $n; $i++)
$gcd = ___gcd($gcd, $arr[$i]);
return ($gcd == 1)? $n : -1;
}
// Driver code
$arr = array(1, 3, 5, 7);
$n = count($arr);
echo "Length of the " .
"largest subarray = " .
findLargest($arr, $n);
// This code is contributed by Sam007
?>
Javascript
<script>
// Javascript program, to find length of the
// largest subarray with GCD equals to 1.
function ___gcd(a, b)
{
// Everything divides 0
if (a == 0 || b == 0)
return 0;
// base case
if (a == b)
return a;
// a is greater
if (a > b)
return ___gcd(a - b, b);
return ___gcd(a, b - a);
}
function findLargest(arr, n)
{
/*If gcd of any subarray is 1
then gcd of any number with the
sub array will be 1. so if we
are getting any subarray with
gcd 1, then maximum number of
element of the subarray will
be equal to the number of
elements of the array. Else
it will be -1.*/
let gcd = arr[0];
for (let i = 1; i < n; i++)
gcd = ___gcd(gcd, arr[i]);
return (gcd == 1)? n : -1;
}
// Driver Code
let arr = [1, 3, 5, 7];
let n = arr.length;
document.write("Length of the "
+ "largest subarray = "
+ findLargest(arr, n));
</script>
Producción
Length of the largest subarray = 4
Complejidad de tiempo: O(log(min(n)))
Espacio auxiliar: O(1)
Este artículo es una contribución de Aarti_Rathi y Smarak Chopdar . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA