Minimum array sum after repeatedly subtracting smaller elements

Updated

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)

Comment
Mithlesh Upadhyay Published 21 Nov 2026 · 2 min read

Mithlesh Upadhyay is a Computer Science and AI expert from Madhya Pradesh with strong academic background (BE in CSE and M.Tech in AI) and over six years of experience in technical content development. He has contributed tech articles, led teams, and worked in Full Stack Development and Data Science. He founded the w3colleges.org portal for learning resources.

Related tutorials