Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Solution Approach
3.1.
Approach 1 (Naive)
3.1.1.
C++ Code
3.1.2.
Python Code
3.2.
Approach 2 (Efficient)
3.2.1.
C++ Code
3.2.2.
Python Code
4.
Frequently Asked Questions
4.1.
Can there be two answers to this question?
4.2.
What is the space complexity of the above approach?
4.3.
Can the above problem be solved with a time complexity less than O(n)?
5.
Conclusion 
Last Updated: Mar 27, 2024
Easy

Find an array element such that all elements are divisible by it

Author Pradeep Kumar
1 upvote

Introduction

In this article, we will look at the problem of finding the Array element such that all elements are divisible by it. We will look at two different approaches to solve this problem and compare their time complexities to find out the efficient method.

Problem Statement

Given an array of n elements, we are to find an element such that all the elements of the array are divisible by it. If there exists no such element, print -1.

Examples:

Input:  arr = [24, 15, 7, 6, 9, 10, 12]
Output: -1
Explanation: There exists no such element which is a factor of all the elements. Therefore, the answer is -1.
 
Input:  arr = [9, 15, 18, 102, 3]
Output: 3
Explanation: 3 divides all the elements

Also see, kth largest element in an array and  Euclid GCD Algorithm

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Solution Approach

This problem can be solved in a number of ways. In this article, we will discuss two approaches: a naive method and an efficient method.

Approach 1 (Naive)

In this approach, we pick one element from the array and check if all the elements are divisible by it or not. The algorithm is as follows:

Step 1: Iterate over the array.

Step 2: Pick one element from the array, index-wise.

Step 3: Iterate over the array and check if the picked element divides all the elements.

Step 4: If yes, break the loop, and print the picked element. Otherwise, move to step 2 and pick the next element.

Step 5: If none of the array elements satisfies this condition, print -1.

Algorithm:

for i in 0..n-1:
    for j in 0..n-1:
        if (arr[j]%arr[i] !=0):
            break

    if loop didn't break:
        return arr[i]
   
return -1

The Time complexity of this algorithm is O(n^2). The implementation code for the above approach is as follows:

C++ Code

#include<bits/stdc++.h>
using namespace std;

// Function to find the element which divides all the elements of the array
int findSmallestFactor(int arr[],int n){
    // Iterate over the array
    for(int i=0;i<n;i++){
        // Choose the pivot element
        int pivot = arr[i];
        int j=0;
        for(j;j<n;j++){
            // If the current element is not divisible by pivot, break the loop
            if(arr[j]%pivot!=0){
                break;
            }
        }

        if(j==n){
            // Means the loop didn't break.
            // Therefore the pivot element is the answer.
            return pivot;
        }
    }

    // if no element satisfies the given condition, return -1.
    return -1;
}

int main(){
    // Input array
    const int n = 5; // number of elements in array
    int arr [n] = {9, 15, 18, 102, 3};

    cout<<findSmallestFactor(arr,n)<<endl; // Invoking the function to find the smallest factor that divides all the elements
   
    return 0;
}

Python Code

# Function to find the element which divides all the elements of the array
def findSmallestFactor(arr,n):
    # Iterate over the array
    for i in range(0,n):
        # Choose the pivot element
        pivot = arr[i]
        loopBreak = False # Variable to track if the inner loop breaks or not.
        for j in range(0,n):
            # If the current element is not divisible by pivot, break the loop
            if(arr[j]%pivot!=0):
                loopBreak = True # loop breaks
                break
           
        if(loopBreak == False): # If loop didn't break
            # The pivot element is the answer.
            return pivot;

    # if no element satisfies the given condition, return -1.
    return -1

if __name__=="__main__":
    # Input array
    n= 5 # length of the array
    arr = [9, 15, 18, 102, 3]
    print(findSmallestFactor(arr,n)) # Invoking the function to find the smallest factor that divides all the elements

Output:

3

Approach 2 (Efficient)

The idea of this approach is based on the fact that if a number (let's say x) is to divide another number (let's say y), then x has to be less than or equal to y (i.e., x<=y). Otherwise, x can't divide y.

Since in this problem, one element has to divide all other elements. Therefore, if such an element exists, it will be the minimum element of the array. So instead of checking for all the elements, we can simply check if the minimum element of the array divides all other elements or not. The algorithm is as follows:

Step 1: Find the minimum element of the array.

Step 2: Check if this element divides all the elements or not

Step 3: If yes, return this element as the output. Else, return -1

As we are iterating over the array once, the time complexity of this approach is O(n). The implementation code for the above approach is as follows:

C++ Code

#include<bits/stdc++.h>
using namespace std;

// Function to find the minimum element of the array
int findMinElement(int arr[],int n){
    int minElement = INT_MAX;
    for(int i=0;i<n;i++){
        int currElement = arr[i];
        if(currElement < minElement){
            minElement = currElement;
        }
    }
    return minElement;
}

// Function to find the element which divides all the elements of the array
int findSmallestFactor(int arr[],int n){

    // Take the minimum element as the pivot element
    int pivot = findMinElement(arr,n);
   
    // Iterate over the array
    for(int i=0;i<n;i++){
        // If the current element is not divisible by pivot, break the loop
        if(arr[i]%pivot!=0){
            return -1 ;
        }
    }
    // if every element is divisible by the pivot, return pivot as the output
    return pivot;
}

int main(){
    // Input array
    const int n = 5; // number of elements in array
    int arr [n] = {9, 15, 18, 102, 3};

    cout<<findSmallestFactor(arr,n)<<endl; // Invoking the function to find the smallest factor that divides all the elements
   
    return 0;
}

Python Code

# Function to find the minimum element of the array
from locale import currency


def findMinElement(arr,n):
    minElement = 1e9
    for i in range(n):
        currElement = arr[i]
        if currElement < minElement:
            minElement = currElement
   
    return minElement

# Function to find the element which divides all the elements of the array
def findSmallestFactor(arr,n):

    pivot = findMinElement(arr,n) # pivot element

    # Iterate over the array
    for i in range(0,n):
        # If the current element is not divisible by pivot, return -1
        if(arr[i]%pivot!=0):
            return -1
   
    # if every element is divisible by the pivot, return pivot as the output
    return pivot


if __name__=="__main__":
    # Input array
    n= 5 # length of the array
    arr = [9, 15, 18, 102, 3]
    print(findSmallestFactor(arr,n)) # Invoking the function to find the smallest factor that divides all the elements

Output:

3

Frequently Asked Questions

Can there be two answers to this question?

Let's assume that there are two answers to this question: x and y, such that x!=y (i.e., x is not equal to y). Now since x divides all the elements of the array and y also belongs to the array. Therefore x divides y. And for this divisibility condition to hold x<=y (Eqn 1). Similarly, y divides x, and y<=x (Eqn 2). From Eqn 1 and 2, we get that x is equal to y, which is a contradiction. Hence, there can not be two answers to this question. 

What is the space complexity of the above approach?

The space complexity of the above approach is O(1), as we are only using the unit amount of extra space. This unit space is used to store the variables: pivot, minElement, and currElement.

Can the above problem be solved with a time complexity less than O(n)?

Finding the minimum element in an unsorted array takes O(n) time. Therefore, the problem can not be solved in time less than that.

Conclusion 

In this article, we have extensively discussed the problem of finding an array element such that all elements are divisible by it. We hope that this blog has helped you enhance your knowledge, to learn more, check out this article

Recommended problems -

 

And also, check out the awesome content on the Coding Ninjas Website,
Android DevelopmentCoding Ninjas Studio ProblemsCoding Ninjas Studio Interview BundleCoding Ninjas Studio Interview ExperiencesCoding Ninjas CoursesCoding Ninjas Studio Contests, and Coding Ninjas Studio Test SeriesDo upvote our blog to help other ninjas grow. Happy Coding!

Previous article
Find the first, second, and third minimum elements in an array
Next article
Count of Subarrays in the Range [L, R] having XOR + 1 equal to XOR (XOR) 1 for M Queries
Live masterclass