The given problem involves finding a number X that has all the integers in a given array as its divisors except for 1 and X itself. The array contains N integers that are all divisors of X, and the goal is to find X. If there is no such number, the function should return -1.
To solve this problem, we can use the fact that the product of all the integers in the array will give us X^2. Since we know that each integer in the array is a divisor of X, we can take the square root of X^2 to get X. Therefore, we can multiply all the integers in the array to get X^2, take the square root of X^2 to get X, and then check if all the integers in the array are divisors of X. If they are, we return X, otherwise, we return -1.
To implement this algorithm, we can first sort the array to make sure that the smallest and largest integers are multiplied to get X^2. We can then compute X by taking the square root of the product of all the integers in the array. Finally, we can check if all the integers in the array are divisors of X by iterating through the array and checking if X is divisible by each integer. If X is divisible by all integers in the array, we return X. Otherwise, we return -1.
Examples:Â
Input: arr[] = {2, 10, 5, 4}Â
Output: 20ÂInput: arr[] = {2, 10, 5}Â
Output: 20ÂInput: arr[] = {2, 15}Â
Output: -1Â
Approach: Sort the given N divisors and the number X will be the first number * last number in the sorted array. Cross-check if the X contradicts the given statement or not by storing all the divisors of X except 1 and X in another array and if the formed array and given array are not same then print -1, else print X.
Below is the implementation of the above approach:Â
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;Â
// Function that returns Xint findX(int a[], int n){    // Sort the given array    sort(a, a + n);Â
    // Get the possible X    int x = a[0] * a[n - 1];Â
    // Container to store divisors    vector<int> vec;Â
    // Find the divisors of x    for (int i = 2; i * i <= x; i++)     {        // Check if divisor        if (x % i == 0)         {            vec.push_back(i);            if ((x / i) != i)                vec.push_back(x / i);        }    }         // sort the vec because a is sorted    // and we have to compare all the elements    sort(vec.begin(), vec.end());Â
    // if size of both vectors is not same    // then we are sure that both vectors    // can't be equal    if (vec.size() != n)        return -1;    else    {         // Check if a and vec have        // same elements in them        int i = 0;        for (auto it : vec)         {            if (a[i++] != it)                return -1;        }    }Â
    return x;}Â
// Driver codeint main(){    int a[] = { 2, 5, 4, 10 };    int n = sizeof(a) / sizeof(a[0]);       // Function call    cout << findX(a, n);Â
    return 0;} |
Java
// Java implementation of the approachimport java.util.*;Â
class GFG {Â
    // Function that returns X    static int findX(int a[], int n)    {        // Sort the given array        Arrays.sort(a);Â
        // Get the possible X        int x = a[0] * a[n - 1];Â
        // Container to store divisors        Vector<Integer> vec = new Vector<Integer>();Â
        // Find the divisors of x        for (int i = 2; i * i <= x; i++)         {            // Check if divisor            if (x % i == 0)             {                vec.add(i);                if ((x / i) != i)                    vec.add(x / i);            }        }        // sort the vec because a is sorted        // and we have to compare all the elements        Collections.sort(vec);Â
        // if size of both vectors is not same        // then we are sure that both vectors        // can't be equal        if (vec.size() != n)            return -1;        else {            // Check if a and vec have            // same elements in them            int i = 0;            for (int it : vec) {                if (a[i++] != it)                    return -1;            }        }Â
        return x;    }Â
    // Driver code    public static void main(String[] args)    {        int a[] = { 2, 5, 4, 10 };        int n = a.length;Â
        // Function call        System.out.print(findX(a, n));    }}Â
// This code is contributed by 29AjayKumar |
Python3
# Python3 implementation of the approach# Function that returns Ximport mathÂ
Â
def findX(list, int):    # Sort the given array    list.sort()Â
    # Get the possible X    x = list[0]*list[int-1]Â
    # Container to store divisors    vec = []Â
    # Find the divisors of x    i = 2    while(i * i <= x):        # Check if divisor        if(x % i == 0):            vec.append(i)            if ((x//i) != i):                vec.append(x//i)        i += 1Â
    # sort the vec because a is sorted        # and we have to compare all the elements    vec.sort()    # if size of both vectors is not same    # then we are sure that both vectors    # can't be equal    if(len(vec) != int):        return -1    else:        # Check if a and vec have        # same elements in them        j = 0        for it in range(int):            if(a[j] != vec[it]):                return -1            else:                j += 1    return xÂ
Â
# Driver codea = [2, 5, 4, 10]n = len(a)Â
# Function callprint(findX(a, n)) |
C#
// C# implementation of the approachusing System;using System.Collections.Generic;Â
class GFG {Â
    // Function that returns X    static int findX(int[] a, int n)    {        // Sort the given array        Array.Sort(a);Â
        // Get the possible X        int x = a[0] * a[n - 1];Â
        // Container to store divisors        List<int> vec = new List<int>();Â
        // Find the divisors of a number        for (int i = 2; i * i <= x; i++)        {            // Check if divisor            if (x % i == 0) {                vec.Add(i);                if ((x / i) != i)                    vec.Add(x / i);            }        }Â
        // sort the vec because a is sorted        // and we have to compare all the elements        vec.Sort();Â
        // if size of both vectors is not same        // then we are sure that both vectors        // can't be equal        if (vec.Count != n)         {            return -1;        }        else        {            // Check if a and vec have            // same elements in them            int i = 0;            foreach(int it in vec)            {                if (a[i++] != it)                    return -1;            }        }Â
        return x;    }Â
    // Driver code    public static void Main(String[] args)    {        int[] a = { 2, 5, 4, 10 };        int n = a.Length;               // Function call        Console.Write(findX(a, n));    }}Â
// This code is contributed by 29AjayKumar |
Javascript
<script>Â
// Javascript implementation of the approachÂ
// Function that returns Xfunction findX(a, n){    // Sort the given array    a.sort((x,y) => x - y);Â
    // Get the possible X    let x = a[0] * a[n - 1];Â
    // Container to store divisors    let vec = [];Â
    // Find the divisors of x    for (let i = 2; i * i <= x; i++)     {        // Check if divisor        if (x % i == 0)         {            vec.push(i);            if (parseInt(x / i) != i)                vec.push(parseInt(x / i));        }    }         // sort the vec because a is sorted    // and we have to compare all the elements    vec.sort((x,y) => x - y);Â
    // if size of both vectors is not same    // then we are sure that both vectors    // can't be equal    if (vec.length != n)        return -1;    else    {         // Check if a and vec have        // same elements in them        let i = 0;        for (let j = 0; j < vec.length; j++)         {            if (a[i++] != vec[j])                return -1;        }    }Â
    return x;}Â
// Driver code    let a = [ 2, 5, 4, 10 ];    let n = a.length;       // Function call    document.write(findX(a, n));     </script> |
Output
20
Time Complexity:
- Sorting the array takes O(n log n) time.
- Finding the divisors of x takes O(sqrt(x)) time.
- Sorting the vector takes O(n log n) time.
- Comparing the elements of the vector and array takes O(n) time.
Therefore, the time complexity of the function is O(n log n + sqrt(x) + n log n + n) which can be simplified to O(sqrt(x) + n log n).
Auxiliary Space:
- The function uses a vector to store the divisors of x, which has a maximum size of sqrt(x).
- Therefore, the auxiliary space used by the function is O(sqrt(x)).
Space Complexity:
- The input array has a space complexity of O(n).
- The auxiliary space used by the function is O(sqrt(x)).
- Therefore, the space complexity of the function is O(n + sqrt(x)).
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!
