Given an array of integers. Find an integer X which is the divisor of all except for exactly one element in the given array.
Note: The GCD of all the elements is not 1.
Examples:
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.
Approach: Make a prefix array P such that index i contains the GCD of all the elements from 1 to i. Similarly, make a suffix array S such that index i contains the GCD of all the elements from i to n-1 (last index). If the GCD of P[i-1] and S[i+1] is not the divisor of the element at i, then it is the required answer.
Below is the implementation of the above approach:
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 codeint 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 Codeif __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 codepublic 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 Codevar a = [ 12, 6, 18, 12, 16 ];var n = a.length; document.write(getDivisor(a, n)); // This code is contributed by kirti</script> |
Output
6
Complexity Analysis:
- Time Complexity: O(nlogn)
- Auxiliary Space: O(n)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
