Given an array arr, the task is to find the minimum sum of the elements of the array after applying the following operation:
For any pair from the array, if a[i] > a[j] then a[i] = a[i] – a[j].
Examples:
Input: arr[] = {1, 2, 3}
Output: 3
modified array will be {1, 1, 1}Input: a = {2, 4, 6}
Output: 6
modified array will be {2, 2, 2}
Approach: Observe here that after each operation, the GCD of all the elements will remain the same. So, in the end, every element will be equal to the gcd of all the elements of the array after applying the given operation.
So, the final answer will be (n * gcd).
Below is the implementation of the above approach:
C++
// CPP program to Find the minimum sum// of given array after applying given operation.#include <bits/stdc++.h>using namespace std;// Function to Find the minimum sum// of given array after applying given operation.int MinSum(int a[], int n){ // to store final gcd value int gcd = a[0]; // get gcd of the whole array for (int i = 1; i < n; i++) gcd = __gcd(a[i], gcd); return n * gcd;}// Driver codeint main(){ int a[] = { 20, 14, 6, 8, 15 }; int n = sizeof(a) / sizeof(a[0]); // function call cout << MinSum(a, n); return 0;} |
Java
// Java program to Find the minimum sum// of given array after applying given operation.import java.io.*;class GFG { // Recursive function to return gcd of a and b static int __gcd(int a, int b) { // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // base case if (a == b) return a; // a is greater if (a > b) return __gcd(a-b, b); return __gcd(a, b-a); } // Function to Find the minimum sum// of given array after applying given operation.static int MinSum(int []a, int n){ // to store final gcd value int gcd = a[0]; // get gcd of the whole array for (int i = 1; i < n; i++) gcd = __gcd(a[i], gcd); return n * gcd;}// Driver code public static void main (String[] args) { int a[] = { 20, 14, 6, 8, 15 }; int n = a.length; // function call System.out.println(MinSum(a, n)); }}// This code is contributed by anuj_67.. |
Python3
# Python3 program to Find the minimum # sum of given array after applying # given operation.import math# Function to Find the minimum sum# of given array after applying # given operation.def MinSum(a, n): # to store final gcd value gcd = a[0] # get gcd of the whole array for i in range(1, n): gcd = math.gcd(a[i], gcd) return n * gcd# Driver codeif __name__ == "__main__": a = [20, 14, 6, 8, 15 ] n = len(a) # function call print(MinSum(a, n))# This code is contributed by ita_c |
C#
// C# program to Find the minimum sum// of given array after applying given operation.using System;class GFG { // Recursive function to return gcd of a and b static int __gcd(int a, int b) { // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // base case if (a == b) return a; // a is greater if (a > b) return __gcd(a-b, b); return __gcd(a, b-a); } // Function to Find the minimum sum // of given array after applying given operation. static int MinSum(int []a, int n) { // to store final gcd value int gcd = a[0]; // get gcd of the whole array for (int i = 1; i < n; i++) gcd = __gcd(a[i], gcd); return n * gcd; } // Driver Program to test above function static void Main() { int []a = { 20, 14, 6, 8, 15 }; int n = a.Length; Console.WriteLine(MinSum(a, n)); } // This code is contributed by Ryuga.} |
PHP
<?php// PHP program to Find the minimum sum of// given array after applying given operation.// Function to Find the minimum sum// of given array after applying// given operation.function gcd($a, $b) { if ($b == 0) return $a; return gcd($b, $a % $b); } function MinSum($a, $n){ // to store final gcd value $gcdd = $a[0]; // get gcd of the whole array for ($i = 1; $i < $n; $i++) $gcdd = gcd($a[$i], $gcdd); return $n * $gcdd;}// Driver code$a = array( 20, 14, 6, 8, 15 );$n = count($a);// function callecho MinSum($a, $n);// This code is contributed by mits?> |
Javascript
<script>// Javascript program to Find the minimum sum// of given array after applying given operation.// Recursive function to return gcd of a and b function __gcd(a, b) { // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // base case if (a == b) return a; // a is greater if (a > b) return __gcd(a - b, b); return __gcd(a, b - a); } // Function to Find the minimum sum// of given array after applying // given operation.function MinSum(a, n){ // To store final gcd value var gcd = a[0]; // Get gcd of the whole array for(var i = 1; i < n; i++) gcd = __gcd(a[i], gcd); return n * gcd;}// Driver codevar a = [ 20, 14, 6, 8, 15 ];var n = a.length;// Function calldocument.write( MinSum(a, n));// This code is contributed by noob2000</script> |
Output:
5
Time Complexity: O(n * log(min(a, b))), where a and b are two parameters of the gcd.
Auxiliary Space: O(log(min(a, b)))
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!