Given an array of integers A. The task is to minimize the sum of the elements of the array using the following rule:
Choose two indices i and j and an arbitrary integer x, such that x is a divisor of A[i] and change them as following A[i] = A[i]/x and A[j] = A[j]*x.
Examples:
Input: A = { 1, 2, 3, 4, 5 }
Output: 14
Divide A[3] by 2 then
A[3] = 4/2 = 2,
Multiply A[0] by 2 then
A[0] = 1*2 = 2
Updated array A = { 2, 2, 3, 2, 5 }
Hence sum = 14
Input: A = { 2, 4, 2, 3, 7 }
Output: 18
Approach: If any number is divided by x then it is optimal to multiply the x with the smallest number present in the array.
The idea is to get the minimum of the array and find the divisors of the particular element and keep checking that by how much the sum is reduced.
Below is the implementation of the above approach:
C++
// C++ implementation#include <bits/stdc++.h>using namespace std;// Function to return the minimum sumvoid findMin(int arr[], int n){ int sum = 0; for (int i = 0; i < n; i++) sum += arr[i]; // sort the array to find the // minimum element sort(arr, arr + n); int min = arr[0]; int max = 0; for (int i = n - 1; i >= 1; i--) { int num = arr[i]; int total = num + min; int j; // finding the number to // divide for (j = 2; j <= num; j++) { if (num % j == 0) { int d = j; int now = (num / d) + (min * d); // Checking to what // instance the sum // has decreased int reduce = total - now; // getting the max // difference if (reduce > max) max = reduce; } } } cout << (sum - max);}// Driver Codeint main(){ int arr[] = { 1, 2, 3, 4, 5 }; int n = sizeof(arr) / sizeof(arr[0]); findMin(arr, n);} |
Java
// Java implementation of the above approachimport java.util.*;class GFG { // Function to return the minimum sum static void findMin(int arr[], int n) { int sum = 0; for (int i = 0; i < n; i++) sum += arr[i]; // sort the array to find the // minimum element Arrays.sort(arr); int min = arr[0]; int max = 0; for (int i = n - 1; i >= 1; i--) { int num = arr[i]; int total = num + min; int j; // finding the number to // divide for (j = 2; j <= num; j++) { if (num % j == 0) { int d = j; int now = (num / d) + (min * d); // Checking to what // instance the sum // has decreased int reduce = total - now; // getting the max // difference if (reduce > max) max = reduce; } } } System.out.println(sum - max); } // Driver Code public static void main (String[] args) { int arr[] = { 1, 2, 3, 4, 5 }; int n = arr.length; findMin(arr, n); }}// This code is contributed by AnkitRai01 |
Python3
# Function to return the minimum sum def findMin(arr, n): sum = 0 for i in range(0, n): sum = sum + arr[i] # sort the array to find the # minimum element arr.sort() min = arr[0] max = 0 for i in range(n - 1, 0, -1): num = arr[i] total = num + min # finding the number to # divide for j in range(2, num + 1): if(num % j == 0): d = j now = (num // d) + (min * d) # Checking to what # instance the sum # has decreased reduce = total - now # getting the max # difference if(reduce > max): max = reduce print(sum - max)# Driver Code arr = [1, 2, 3, 4, 5 ]n = len(arr)findMin(arr, n)# This code is contributed by Sanjit_Prasad |
C#
// C# implementation of the above approachusing System; class GFG { // Function to return the minimum sum static void findMin(int []arr, int n) { int sum = 0; for (int i = 0; i < n; i++) sum += arr[i]; // sort the array to find the // minimum element Array.Sort(arr); int min = arr[0]; int max = 0; for (int i = n - 1; i >= 1; i--) { int num = arr[i]; int total = num + min; int j; // finding the number to // divide for (j = 2; j <= num; j++) { if (num % j == 0) { int d = j; int now = (num / d) + (min * d); // Checking to what // instance the sum // has decreased int reduce = total - now; // getting the max // difference if (reduce > max) max = reduce; } } } Console.WriteLine(sum - max); } // Driver Code public static void Main (String[] args) { int []arr = { 1, 2, 3, 4, 5 }; int n = arr.Length; findMin(arr, n); }}// This code is contributed by PrinciRaj1992 |
Javascript
<script>// Javascript implementation// Function to return the minimum sumfunction findMin(arr, n){ let sum = 0; for (let i = 0; i < n; i++) sum += arr[i]; // sort the array to find the // minimum element arr.sort(); let min = arr[0]; let max = 0; for (let i = n - 1; i >= 1; i--) { let num = arr[i]; let total = num + min; let j; // finding the number to // divide for (j = 2; j <= num; j++) { if (num % j == 0) { let d = j; let now = parseInt(num / d) + (min * d); // Checking to what // instance the sum // has decreased let reduce = total - now; // getting the max // difference if (reduce > max) max = reduce; } } } document.write(sum - max);}// Driver Code let arr = [ 1, 2, 3, 4, 5 ]; let n = arr.length; findMin(arr, n);</script> |
Output:
14
Time Complexity: O((N * logN) + (N * M)), where N is the size of the given array and M is the maximum element in the array.
Auxiliary Space: O(1), no extra space is required, so it is a constant.
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!
