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>
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