Dada una array de enteros. Encuentre un entero X que sea el divisor de todos excepto exactamente un elemento en la array dada.
Nota : El MCD de todos los elementos no es 1.
Ejemplos:
Input : arr[] = {6, 18, 3, 12}
Output : 6
6 is the divisor of all except 3.
Input : arr[] = {40, 15, 30, 42}
Output : 3
3 is the divisor of all except 40.
Enfoque: haga una array de prefijos P tal que el índice i contenga el GCD de todos los elementos del 1 al i. De manera similar, haga una array de sufijos S tal que el índice i contenga el GCD de todos los elementos desde i hasta n-1 (último índice). Si el MCD de P[i-1] y S[i+1] no es el divisor del elemento en i, entonces es la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the divisor of all
// except for exactly one element in an array.
#include <bits/stdc++.h>
using namespace std;
// Function that returns the divisor of all
// except for exactly one element in an array.
int getDivisor(int a[], int n)
{
// There's only one element in the array
if (n == 1)
return (a[0] + 1);
int P[n], S[n];
// Creating prefix array of GCD
P[0] = a[0];
for (int i = 1; i < n; i++)
P[i] = __gcd(a[i], P[i - 1]);
// Creating suffix array of GCD
S[n-1] = a[n-1];
for (int i = n - 2; i >= 0; i--)
S[i] = __gcd(S[i + 1], a[i]);
// Iterate through the array
for (int i = 0; i <= n; i++) {
// Variable to store the divisor
int cur;
// Getting the divisor
if (i == 0)
cur = S[i + 1];
else if (i == n - 1)
cur = P[i - 1];
else
cur = __gcd(P[i - 1], S[i + 1]);
// Check if it is not a divisor of a[i]
if (a[i] % cur != 0)
return cur;
}
return 0;
}
// Driver code
int main()
{
int a[] = { 12, 6, 18, 12, 16 };
int n = sizeof(a) / sizeof(a[0]);
cout << getDivisor(a, n);
return 0;
}
Java
// Java program to find the divisor of all
// except for exactly one element in an array.
import java.io.*;
class GFG {
// Recursive function to return gcd of a and b
static int __gcd(int a, int b)
{
// Everything divides 0
if (a == 0)
return b;
if (b == 0)
return a;
// base case
if (a == b)
return a;
// a is greater
if (a > b)
return __gcd(a-b, b);
return __gcd(a, b-a);
}
// Function that returns the divisor of all
// except for exactly one element in an array.
static int getDivisor(int a[], int n)
{
// There's only one element in the array
if (n == 1)
return (a[0] + 1);
int P[] = new int[n];
int S[] = new int[n];
// Creating prefix array of GCD
P[0] = a[0];
for (int i = 1; i < n; i++)
P[i] = __gcd(a[i], P[i - 1]);
// Creating suffix array of GCD
S[n-1] = a[n-1];
for (int i = n - 2; i >= 0; i--)
S[i] = __gcd(S[i + 1], a[i]);
// Iterate through the array
for (int i = 0; i < n; i++) {
// Variable to store the divisor
int cur;
// Getting the divisor
if (i == 0)
cur = S[i + 1];
else if (i == n - 1)
cur = P[i - 1];
else
cur = __gcd(P[i - 1], S[i + 1]);
// Check if it is not a divisor of a[i]
if (a[i] % cur != 0)
return cur;
}
return 0;
}
// Driver code
public static void main (String[] args) {
int a[] = { 12, 6, 18, 12, 16 };
int n = a.length;
System.out.println(getDivisor(a, n));
}
}
// This code is contributed by anuj_67..
Python 3
# Python 3 program to find the divisor of all # except for exactly one element in an array. from math import gcd # Function to find the divisor of all # except for exactly one element in an array. def getDivisor(a, n): # There's only one element in the array if (n == 1): return (a[0] + 1) P = [0] * n S = [0] * n # Creating prefix array of GCD P[0] = a[0] for i in range(1, n): P[i] = gcd(a[i], P[i - 1]) # Creating suffix array of GCD S[n - 1] = a[n - 1] for i in range(n - 2, -1, -1): S[i] = gcd(S[i + 1], a[i]) # Iterate through the array for i in range(0, n + 1): # Variable to store the divisor cur = 0 # Getting the divisor if (i == 0): cur = S[i + 1] elif (i == n - 1): cur = P[i - 1] else: cur = gcd(P[i - 1], S[i + 1]) # Check if it is not a divisor of a[i] if (a[i] % cur != 0): return cur return 0; # Driver Code if __name__=='__main__': a = [12, 6, 18, 12, 16] n = len(a) print(getDivisor(a, n)) # This code is contributed by Rupesh Rao
C#
// C# program to find the divisor of all
// except for exactly one element in an array.
using System;
class GFG
{
// Recursive function to return gcd of a and b
static int __gcd(int a, int b)
{
// Everything divides 0
if (a == 0)
return b;
if (b == 0)
return a;
// base case
if (a == b)
return a;
// a is greater
if (a > b)
return __gcd(a - b, b);
return __gcd(a, b - a);
}
// Function that returns the divisor of all
// except for exactly one element in an array.
static int getDivisor(int[] a, int n)
{
// There's only one element in the array
if (n == 1)
return (a[0] + 1);
int[] P = new int[n];
int[] S = new int[n];
// Creating prefix array of GCD
P[0] = a[0];
for (int i = 1; i < n; i++)
P[i] = __gcd(a[i], P[i - 1]);
// Creating suffix array of GCD
S[n - 1] = a[n - 1];
for (int i = n - 2; i >= 0; i--)
S[i] = __gcd(S[i + 1], a[i]);
// Iterate through the array
for (int i = 0; i <= n; i++)
{
// Variable to store the divisor
int cur;
// Getting the divisor
if (i == 0)
cur = S[i + 1];
else if (i == n - 1)
cur = P[i - 1];
else
cur = __gcd(P[i - 1], S[i + 1]);
// Check if it is not a divisor of a[i]
if (a[i] % cur != 0)
return cur;
}
return 0;
}
// Driver code
public static void Main ()
{
int[] a = { 12, 6, 18, 12, 16 };
int n = a.Length;
Console.WriteLine(getDivisor(a, n));
}
}
// This code is contributed
// by Akanksha Rai
PHP
<?php
// PHP program to find the divisor of all
// except for exactly one element in an array.
// Recursive function to return
// gcd of a and b
function __gcd($a, $b)
{
// Everything divides 0
if ($a == 0)
return b;
if ($b == 0)
return $a;
// base case
if ($a == $b)
return $a;
// a is greater
if ($a > $b)
return __gcd($a - $b, $b);
return __gcd($a, $b - $a);
}
// Function that returns the divisor of all
// except for exactly one element in an array.
function getDivisor($a, $n)
{
// There's only one element in the array
if ($n == 1)
return ($a[0] + 1);
$P = array() ;
$S = array() ;
// Creating prefix array of GCD
$P[0] = $a[0];
for ($i = 1; $i < $n; $i++)
$P[$i] = __gcd($a[$i], $P[$i - 1]);
// Creating suffix array of GCD
$S[$n - 1] = $a[$n - 1];
for ($i = $n - 2; $i >= 0; $i--)
$S[$i] = __gcd($S[$i + 1], $a[$i]);
// Iterate through the array
for ($i = 0; $i <= $n; $i++)
{
// Getting the divisor
if ($i == 0)
$cur = $S[$i + 1];
else if ($i == $n - 1)
$cur = $P[$i - 1];
else
$cur = __gcd($P[$i - 1], $S[$i + 1]);
// Check if it is not a divisor of a[i]
if ($a[$i] % $cur != 0)
return $cur;
}
return 0;
}
// Driver code
$a = array( 12, 6, 18, 12, 16 );
$n = sizeof($a);
echo getDivisor($a, $n);
// This code is contributed by Ryuga
?>
Javascript
<script>
// Javascript program to find the
// divisor of all except for exactly
// one element in an array.
// Recursive function to return gcd of a and b
function __gcd(a, b)
{
// Everything divides 0
if (a == 0)
return b;
if (b == 0)
return a;
// base case
if (a == b)
return a;
// a is greater
if (a > b)
return __gcd(a-b, b);
return __gcd(a, b-a);
}
// Function that returns the divisor of all
// except for exactly one element in an array.
function getDivisor(a, n)
{
// There's only one element in the array
if (n == 1)
return (a[0] + 1);
var P = new Array(n);
var S = new Array(n);
// Creating prefix array of GCD
P[0] = a[0];
for(var i = 1; i < n; i++)
P[i] = __gcd(a[i], P[i - 1]);
// Creating suffix array of GCD
S[n-1] = a[n-1];
for (var i = n - 2; i >= 0; i--)
S[i] = __gcd(S[i + 1], a[i]);
// Iterate through the array
for (var i = 0; i < n; i++) {
// Variable to store the divisor
var cur;
// Getting the divisor
if (i == 0)
cur = S[i + 1];
else if (i == n - 1)
cur = P[i - 1];
else
cur = __gcd(P[i - 1], S[i + 1]);
// Check if it is not a divisor of a[i]
if (a[i] % cur != 0)
return cur;
}
return 0;
}
// Driver Code
var a = [ 12, 6, 18, 12, 16 ];
var n = a.length;
document.write(getDivisor(a, n));
// This code is contributed by kirti
</script>
Producción:
6
Complejidad de tiempo: O (nlogn)
Espacio Auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por rupesh_rao y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA