Find number from its divisors

Namachila November 19, 2025

0 0 6 minutes read

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 X
int 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 code
int 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 approach
import 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 X
import 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 code
a = [2, 5, 4, 10]
n = len(a)
 
# Function call
print(findX(a, n))

C#

// C# implementation of the approach
using 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 X
function 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

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