Given an array arr, replace any one element in array with any other integer. The task is to return the maximum number which divides all elements in this array completely.
Examples:
Input: arr = [15, 9, 3]
Output: 3
Explanation: Here replace 15 with 3 so array becomes arr = [3, 9, 3] and now all elements in array are divisible by 3, so 3 is our answerInput: arr = [16, 5, 10, 25]
Output: 5
Approach: To solve the above problem:
- Iterate the array over integer i from zero to less than its length
- Each time, remove ith element from the array and find the greatest common divisor and store in variable the gcd
- Update maxGcd if current gcd is greater than maxGcd
Below is the implementation of the above approach:
C++14
// C++ Implementation for the above approach#include <bits/stdc++.h>using namespace std;// Function to return gcd of two numbersint gcdOfTwoNos(int num1, int num2){ // If one of numbers is 0 // then gcd is other number if (num1 == 0) return num2; if (num2 == 0) return num1; // If both are equal // then that value is gcd if (num1 == num2) return num1; // One is greater if (num1 > num2) return gcdOfTwoNos(num1 - num2, num2); return gcdOfTwoNos(num1, num2 - num1);}// Function to return minimum sumint Min_sum(int arr[], int N){ // Initialize min_sum with large value int min_sum = 1000000, maxGcd = 1; for (int i = 0; i < N; i++) { // Initialize variable gcd int gcd; if (i == 0) gcd = arr[1]; else { gcd = arr[i - 1]; } for (int j = 0; j < N; j++) { if (j != i) gcd = gcdOfTwoNos(gcd, arr[j]); } // Storing value of arr[i] in c int c = arr[i]; // Update maxGcd if gcd is greater // than maxGcd if (gcd > maxGcd) maxGcd = gcd; } // returning the maximum divisor // of all elements return maxGcd;}// Driver codeint main(){ int arr[] = { 16, 5, 10, 25 }; int N = sizeof(arr) / sizeof(int); cout << Min_sum(arr, N); return 0;} |
Java
// Java program for the above approach import java.io.*;class GFG { // Function to return gcd of two numbersstatic int gcdOfTwoNos(int num1, int num2){ // If one of numbers is 0 // then gcd is other number if (num1 == 0) return num2; if (num2 == 0) return num1; // If both are equal // then that value is gcd if (num1 == num2) return num1; // One is greater if (num1 > num2) return gcdOfTwoNos(num1 - num2, num2); return gcdOfTwoNos(num1, num2 - num1);}// Function to return minimum sumstatic int Min_sum(int arr[], int N){ // Initialize min_sum with large value int min_sum = 1000000, maxGcd = 1; for (int i = 0; i < N; i++) { // Initialize variable gcd int gcd; if (i == 0) gcd = arr[1]; else { gcd = arr[i - 1]; } for (int j = 0; j < N; j++) { if (j != i) gcd = gcdOfTwoNos(gcd, arr[j]); } // Storing value of arr[i] in c int c = arr[i]; // Update maxGcd if gcd is greater // than maxGcd if (gcd > maxGcd) maxGcd = gcd; } // returning the maximum divisor // of all elements return maxGcd;} // Driver code public static void main (String[] args) { int arr[] = { 16, 5, 10, 25 }; int N = arr.length; System.out.println( Min_sum(arr, N)); }}// This code is contributed by Potta Lokesh |
Python3
# Python 3 Implementation for the above approach# Function to return gcd1 of two numbersdef gcd1OfTwoNos(num1, num2): # If one of numbers is 0 # then gcd1 is other number if (num1 == 0): return num2 if (num2 == 0): return num1 # If both are equal # then that value is gcd1 if (num1 == num2): return num1 # One is greater if (num1 > num2): return gcd1OfTwoNos(num1 - num2, num2) return gcd1OfTwoNos(num1, num2 - num1)# Function to return minimum sumdef Min_sum(arr, N): # Initialize min_sum with large value min_sum = 1000000 maxgcd1 = 1 for i in range(N): # Initialize variable gcd1 gcd1 = 1 if (i == 0): gcd1 = arr[1] else: gcd1 = arr[i - 1] for j in range(N): if (j != i): gcd1 = gcd1OfTwoNos(gcd1, arr[j]) # Storing value of arr[i] in c c = arr[i] # Update maxgcd1 if gcd1 is greater # than maxgcd1 if (gcd1 > maxgcd1): maxgcd1 = gcd1 # returning the maximum divisor # of all elements return maxgcd1# Driver codeif __name__ == '__main__': arr = [16, 5, 10, 25] N = len(arr) print(Min_sum(arr, N)) # This code is contributed by SURENDRA_GANGWAR. |
C#
// C# program for the above approach using System;public class GFG { // Function to return gcd of two numbersstatic int gcdOfTwoNos(int num1, int num2){ // If one of numbers is 0 // then gcd is other number if (num1 == 0) return num2; if (num2 == 0) return num1; // If both are equal // then that value is gcd if (num1 == num2) return num1; // One is greater if (num1 > num2) return gcdOfTwoNos(num1 - num2, num2); return gcdOfTwoNos(num1, num2 - num1);}// Function to return minimum sumstatic int Min_sum(int []arr, int N){ // Initialize min_sum with large value int min_sum = 1000000, maxGcd = 1; for (int i = 0; i < N; i++) { // Initialize variable gcd int gcd; if (i == 0) gcd = arr[1]; else { gcd = arr[i - 1]; } for (int j = 0; j < N; j++) { if (j != i) gcd = gcdOfTwoNos(gcd, arr[j]); } // Update maxGcd if gcd is greater // than maxGcd if (gcd > maxGcd) maxGcd = gcd; } // returning the maximum divisor // of all elements return maxGcd;} // Driver code public static void Main (string[] args) { int []arr = { 16, 5, 10, 25 }; int N = arr.Length; Console.WriteLine(Min_sum(arr, N)); }}// This code is contributed by AnkThon |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to return gcd of two numbersfunction gcdOfTwoNos(num1, num2){ // If one of numbers is 0 // then gcd is other number if (num1 == 0) return num2; if (num2 == 0) return num1; // If both are equal // then that value is gcd if (num1 == num2) return num1; // One is greater if (num1 > num2) return gcdOfTwoNos(num1 - num2, num2); return gcdOfTwoNos(num1, num2 - num1);}// Function to return minimum sumfunction Min_sum(arr, N){ // Initialize min_sum with large value let min_sum = 1000000, maxGcd = 1; for (let i = 0; i < N; i++) { // Initialize variable gcd let gcd; if (i == 0) gcd = arr[1]; else { gcd = arr[i - 1]; } for (let j = 0; j < N; j++) { if (j != i) gcd = gcdOfTwoNos(gcd, arr[j]); } // Storing value of arr[i] in c let c = arr[i]; // Update maxGcd if gcd is greater // than maxGcd if (gcd > maxGcd) maxGcd = gcd; } // returning the maximum divisor // of all elements return maxGcd;} // Driver Code let arr = [ 16, 5, 10, 25 ]; let N = arr.length; document.write( Min_sum(arr, N));// This code is contributed by sanjoy_62. </script> |
Output:
5
Time Complexity: O((N^2) * Log(M)), Where M is minimum value in array
Auxiliary Space: O(1)
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!