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

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

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!

Live masterclass