Minimum sum formed by digits

December 30, 2021

Minimum sum formed by digits

In Minimum sum formed by digits Problem we have to divide elements of array into two parts such that the sum of numbers formed by the two parts is minimum possible. The problem can be optimally solved using greedy approach. In this article, we will provide an explanation with C++ code.

Minimum Sum Formed By Digits of array Problem Decription

Minimum Sum Formed By Digits of array Problem Description

Given an array of n integers such that each array element is a single digit number. Divide the array elements into exactly two parts such that the sum of numbers formed by the two parts is minimum possible. Output the minimum sum.

Input

  • First Line contains a single integer n – the size of the array.
  • Second line contains n integers – the array elements.

Output

  • The minimum sum.

Minimum Sum Formed By Digits of array Solution

The problem can be optimally solved using greedy technique. We have to divide the array into two parts so that the sum of numbers formed by the two parts is minimum. We can do this by sorting the array in increasing order an taking alternative elements into number 1 and number 2 from smallest to largest number.

Steps –

  • Sort the array in increasing order.
  • Iterate linearly on the array elements.
  • If at even index append the digit in number 1 else append the digit in number 2.
  • Return the sum of number 1 & number 2.

Time Complexity – O(n)

Space Complexity – O(1)

Code

#include <bits/stdc++.h>
using namespace std;
int minSum(int arr[], int n)
{
    sort(arr, arr + n);

    int num1 = 0, num2 = 0;

    for (int i = 0; i < n; i++)
    {
        if (i % 2 == 0)
            num1 = num1 * 10 + arr[i];
        else
            num2 = num2 * 10 + arr[i];
    }

    return num1 + num2;
}
int main()
{
    int n;
    cin >> n;
    int arr[n];
    for (int i = 0; i < n; i++)
        cin >> arr[i];

    cout << minSum(arr, n) << endl;
    return 0;
}

Output

6
3 2 1 4 5 6
381
Explanation
The numbers are -> 135, 246