Find an integer X which is divisor of all except exactly one element in an array

0 0 7 minutes read

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

Output

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