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 Development, Coding Ninjas Studio Problems, Coding Ninjas Studio Interview Bundle, Coding Ninjas Studio Interview Experiences, Coding Ninjas Courses, Coding Ninjas Studio Contests, and Coding Ninjas Studio Test Series. Do upvote our blog to help other ninjas grow. Happy Coding!