You are given an array arr[] of n positive integers. Now choose two different index i and j such that arr[i] > arr[j] and apply this arr[i] = arr[i]-arr[j] operation as many time as you need. Your task is to make the sum of all numbers present in the array as small as possible.
Examples :
Input : arr[] = {2, 4, 6}
Output : 6
Explanation :
arr[2] = arr[2]-arr[1] , arr[1] = arr[1]-arr[0], after performing
these operations the sum of the array elements will be minimum.
Input : arr[] = {1, 2}
Output : 2
Explanation :
arr[1] = arr[1]-arr[0], after performing this operation the sum of the
array elements will be minimum.
Approach : The given problem can be solved based on the following observation:
- In the optimal solution, all number will be equal. Otherwise If we pick any two elements x and y (x<y) and do the operation y = y-x then we can get a solution.
- If we observe carefully after each operation, the GCD (Greatest common divisor) of all number will remain same. Let’s assume d is the divisor of all elements of arr[], then after the operation, d is still a divisor of all these numbers.
- So all numbers will become the GCD of all elements of arr[].
- The answer will be GCD of all elements of arr[] * number of elements in the arr[] .
Follow the steps below to solve the problem :
1. Initialize a variable ans, to store the first element of the array arr[].
2. Run a for loop from 1 to n-1.
3. In the for loop update ans = GCD(ans,arr[i]).
4. Return ans*n .
Implementation :
/*package whatever //do not write package name here */
import java.io.*;
class Main {
static int minimumSum(int arr[], int n)
{
// store the first element of the array arr[]
int ans = arr[0];
for (int i = 1; i < n; i++) {
// calculate the GCD and update the value of ans
ans = GCD(ans, arr[i]);
}
// return ans
return ans*n ;
}
public static void main(String[] args)
{
// no. of elements present in the array
int n = 3;
// given array
int arr[] = { 2, 4, 6 };
// print result
System.out.println(minimumSum(arr, n));
}
// To calculate Greatest common divisor (GCD)
public static int GCD(int a, int b)
{
if (b == 0)
return a;
return GCD(b, a % b);
}
}
Output :
6
Time Complexity : O(N)