Given an array of n non-negative integers. Find such element in the array, that all array elements are divisible by it.
Examples :
Input : arr[] = {2, 2, 4}
Output : 2Input : arr[] = {2, 1, 3, 1, 6}
Output : 1Input: arr[] = {2, 3, 5}
Output : -1
Brute Force Approach:
The brute force approach to solve this problem would be to iterate through all the elements of the array and check if any of them can divide all other elements of the array. If such a number is found, return it as the answer. Otherwise, return -1 as no such number exists.
Below is the implementation of the above approach:
C++
// CPP program to find such number in the array// that all array elements are divisible by it#include <bits/stdc++.h>using namespace std;// Function to return the// desired number if existsint findNumber(int arr[], int n){ for (int i = 0; i < n; i++) { int j; for (j = 0; j < n; j++) if (arr[j] % arr[i] != 0) break; if (j == n) return arr[i]; } return -1;}// Driver Functionint main(){ int arr[] = { 2, 2, 4 }; int n = sizeof(arr) / sizeof(arr[0]); cout << findNumber(arr, n) << endl; return 0;} |
Java
import java.util.*;public class Main { // Function to return the // desired number if exists static int findNumber(int arr[], int n) { for (int i = 0; i < n; i++) { int j; for (j = 0; j < n; j++) { if (arr[j] % arr[i] != 0) break; } if (j == n) return arr[i]; } return -1; } // Driver Function public static void main(String[] args) { int arr[] = { 2, 2, 4 }; int n = arr.length; System.out.println(findNumber(arr, n)); }} |
Python3
# Function to return the# desired number if existsdef findNumber(arr): n = len(arr) for i in range(n): j = 0 while j < n: if arr[j] % arr[i] != 0: break j += 1 if j == n: return arr[i] return -1# Driver Functionarr = [2, 2, 4]print(findNumber(arr)) |
C#
using System;class MainClass { // Function to return the // desired number if exists public static int FindNumber(int[] arr) { for (int i = 0; i < arr.Length; i++) { int j; for (j = 0; j < arr.Length; j++) if (arr[j] % arr[i] != 0) break; if (j == arr.Length) return arr[i]; } return -1; } // Driver Function public static void Main(string[] args) { int[] arr = { 2, 2, 4 }; Console.WriteLine(FindNumber(arr)); }} |
Javascript
// Function to return the desired number if existsfunction findNumber(arr, n) { for (let i = 0; i < n; i++) { let j; for (j = 0; j < n; j++) if (arr[j] % arr[i] != 0) break; if (j == n) return arr[i]; } return -1;}let arr = [2, 2, 4];let n = arr.length;console.log(findNumber(arr, n)); |
Output: 2
Time Complexity: O(N^2)
Space Complexity: O(1)
The approach is to calculate GCD of the entire array and then check if there exist an element equal to the GCD of the array. For calculating the gcd of the entire array we will use Euclidean algorithm.
Implementation:
C++
// CPP program to find such number in the array// that all array elements are divisible by it#include <bits/stdc++.h>using namespace std;// Returns gcd of two numbers.int gcd(int a, int b){ if (a == 0) return b; return gcd(b % a, a);}// Function to return the// desired number if existsint findNumber(int arr[], int n){ // Find GCD of array int ans = arr[0]; for (int i = 0; i < n; i++) ans = gcd(ans, arr[i]); // Check if GCD is present in array for (int i = 0; i < n; i++) if (arr[i] == ans) return ans; return -1;}// Driver Functionint main(){ int arr[] = { 2, 2, 4 }; int n = sizeof(arr) / sizeof(arr[0]); cout << findNumber(arr, n) << endl; return 0;} |
Java
// JAVA program to find such number in// the array that all array elements// are divisible by itimport java.io.*;class GFG { // Returns GCD of two numbers static int gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a); } // Function to return the desired // number if exists static int findNumber(int arr[], int n) { // Find GCD of array int ans = arr[0]; for (int i = 0; i < n; i++) ans = gcd(ans, arr[i]); // Check if GCD is present in array for (int i = 0; i < n; i++) if (arr[i] == ans) return ans; return -1; } // Driver Code public static void main(String args[]) { int arr[] = { 2, 2, 4 }; int n = arr.length; System.out.println(findNumber(arr, n)); }}// This code is contributed by Nikita Tiwari |
Python3
# Python3 program to find such number # in the array that all array # elements are divisible by it# Returns GCD of two numbersdef gcd (a, b) : if (a == 0) : return b return gcd (b % a, a) # Function to return the desired # number if existsdef findNumber (arr, n) : # Find GCD of array ans = arr[0] for i in range(0, n) : ans = gcd (ans, arr[i]) # Check if GCD is present in array for i in range(0, n) : if (arr[i] == ans) : return ans return -1 # Driver Codearr = [2, 2, 4];n = len(arr)print(findNumber(arr, n))# This code is contributed by Nikita Tiwari |
Javascript
<script> // Javascript program to find such number in the array // that all array elements are divisible by it // Returns gcd of two numbers. function gcd(a, b) { if (a == 0) return b; return gcd(b % a, a); } // Function to return the // desired number if exists function findNumber(arr, n) { // Find GCD of array let ans = arr[0]; for (let i = 0; i < n; i++) ans = gcd(ans, arr[i]); // Check if GCD is present in array for (let i = 0; i < n; i++) if (arr[i] == ans) return ans; return -1; } let arr = [ 2, 2, 4 ]; let n = arr.length; document.write(findNumber(arr, n));</script> |
C#
// C# program to find such number in// the array that all array elements// are divisible by itusing System;class GFG { // Returns GCD of two numbers static int gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a); } // Function to return the desired // number if exists static int findNumber(int[] arr, int n) { // Find GCD of array int ans = arr[0]; for (int i = 0; i < n; i++) ans = gcd(ans, arr[i]); // Check if GCD is present in array for (int i = 0; i < n; i++) if (arr[i] == ans) return ans; return -1; } // Driver Code public static void Main() { int[] arr = { 2, 2, 4 }; int n = arr.Length; Console.WriteLine(findNumber(arr, n)); }}// This code is contributed by vt_m |
PHP
<?php// PHP program to find such// number in the array that// all array elements are // divisible by it// Returns gcd of two numbersfunction gcd ($a, $b){ if ($a == 0) return $b; return gcd ($b % $a, $a);}// Function to return the // desired number if existsfunction findNumber ($arr, $n){ // Find GCD of array $ans = $arr[0]; for ($i = 0; $i < $n; $i++) $ans = gcd ($ans, $arr[$i]); // Check if GCD is // present in array for ($i = 0; $i < $n; $i++) if ($arr[$i] == $ans) return $ans; return -1;}// Driver Code$arr =array (2, 2, 4);$n = sizeof($arr);echo findNumber($arr, $n), "\n";// This code is contributed by ajit?> |
Output
2
Time complexity: O(n*logn)
Auxiliary space: O(Amax), where Amax is the maximum element in the given array.
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!
