Suma mínima de dos números formados a partir de dígitos de una array – Part 1

Dada una array de dígitos (los valores son del 0 al 9), encuentre la suma mínima posible de dos números formados a partir de los dígitos de la array. Todos los dígitos de la array dada deben usarse para formar los dos números. 
Ejemplos: 
 

Input: [6, 8, 4, 5, 2, 3]
Output: 604
The minimum sum is formed by numbers 
358 and 246

Input: [5, 3, 0, 7, 4]
Output: 82
The minimum sum is formed by numbers 
35 and 047 

Se formará un número mínimo a partir de un conjunto de dígitos cuando el dígito más pequeño aparezca en la posición más significativa y el siguiente dígito más pequeño aparezca en la siguiente posición más significativa y así sucesivamente. La idea es
ordenar la array en orden creciente y construir dos números alternando la selección dígitos de la array. Entonces, el primer número está formado por dígitos presentes en posiciones impares en la array y el segundo número está formado por dígitos de posiciones pares en la array. Finalmente, devolvemos la suma del primer y segundo número.
A continuación se muestra la implementación de la idea anterior. 
 

C++

// C++ program to find minimum sum of two numbers
// formed from digits of the array.
#include <bits/stdc++.h>
using namespace std;
 
// Function to find and return minimum sum of
// two numbers formed from digits of the array.
int solve(int arr[], int n)
{
    // sort the array
    sort(arr, arr + n);
 
    // let two numbers be a and b
    int a = 0, b = 0;
    for (int i = 0; i < n; i++)
    {
        // fill a and b with every alternate digit
        // of input array
        if (i & 1)
            a = a*10 + arr[i];
        else
            b = b*10 + arr[i];
    }
 
    // return the sum
    return a + b;
}
 
// Driver code
int main()
{
    int arr[] = {6, 8, 4, 5, 2, 3};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Sum is " << solve(arr, n);
    return 0;
}

Java

// Java program to find minimum sum of two numbers
// formed from digits of the array.
import java.util.Arrays;
 
class GFG {
     
    // Function to find and return minimum sum of
    // two numbers formed from digits of the array.
    static int solve(int arr[], int n)
    {
         
        // sort the array
        Arrays.sort(arr);
     
        // let two numbers be a and b
        int a = 0, b = 0;
        for (int i = 0; i < n; i++)
        {
             
            // fill a and b with every alternate
            // digit of input array
            if (i % 2 != 0)
                a = a * 10 + arr[i];
            else
                b = b * 10 + arr[i];
        }
     
        // return the sum
        return a + b;
    }
     
    //driver code
    public static void main (String[] args)
    {
        int arr[] = {6, 8, 4, 5, 2, 3};
        int n = arr.length;
         
        System.out.print("Sum is "
                          + solve(arr, n));
    }
}
 
//This code is contributed by Anant Agarwal.

Python3

# Python3 program to find minimum sum of two
# numbers formed from digits of the array.
 
# Function to find and return minimum sum of
# two numbers formed from digits of the array.
def solve(arr, n):
 
    # sort the array
    arr.sort()
 
    # let two numbers be a and b
    a = 0; b = 0
    for i in range(n):
     
        # Fill a and b with every alternate
        # digit of input array
        if (i % 2 != 0):
            a = a * 10 + arr[i]
        else:
            b = b * 10 + arr[i]
 
    # return the sum
    return a + b
 
# Driver code
arr = [6, 8, 4, 5, 2, 3]
n = len(arr)
print("Sum is ", solve(arr, n))
 
# This code is contributed by Anant Agarwal.

C#

// C# program to find minimum
// sum of two numbers formed
// from digits of the array.
using System;
 
class GFG
{
    // Function to find and return
    // minimum sum of two numbers
    // formed from digits of the array.
    static int solve(int []arr, int n)
    {
        // sort the array
        Array.Sort(arr);
      
        // let two numbers be a and b
        int a = 0, b = 0;
        for (int i = 0; i < n; i++)
        {
            // fill a and b with every alternate digit
            // of input array
            if (i % 2 != 0)
                a = a * 10 + arr[i];
            else
                b = b * 10 + arr[i];
        }
      
        // return the sum
        return a + b;
    }
     
    // Driver code
    public static void Main ()
    {
        int []arr = {6, 8, 4, 5, 2, 3};
        int n = arr.Length;
        Console.WriteLine("Sum is " + solve(arr, n));
    }
}
 
// This code is contributed by Anant Agarwal.

PHP

<?php
// PHP program to find minimum
// sum of two numbers formed
// from digits of the array.
 
// Function to find and return
// minimum sum of two numbers
// formed from digits of the array.
function solve($arr, $n)
{
    // sort the array
    sort($arr); sort($arr , $n);
 
    // let two numbers be a and b
    $a = 0; $b = 0;
    for ($i = 0; $i < $n; $i++)
    {
        // fill a and b with every
        // alternate digit of input array
        if ($i & 1)
            $a = $a * 10 + $arr[$i];
        else
            $b = $b * 10 + $arr[$i];
    }
 
    // return the sum
    return $a + $b;
}
 
// Driver code
$arr = array(6, 8, 4, 5, 2, 3);
$n = sizeof($arr);
echo "Sum is " , solve($arr, $n);
     
// This code is contributed by nitin mittal.
?>

Javascript

<script>
 
// Javascript program to find minimum sum of two numbers
// formed from digits of the array.
 
    // Function to find and return minimum sum of
    // two numbers formed from digits of the array.
    function solve(arr, n)
    {
           
        // sort the array
        arr.sort();
       
        // let two numbers be a and b
        let a = 0, b = 0;
        for (let i = 0; i < n; i++)
        {
               
            // fill a and b with every alternate
            // digit of input array
            if (i % 2 != 0)
                a = a * 10 + arr[i];
            else
                b = b * 10 + arr[i];
        }
       
        // return the sum
        return a + b;
    }
 
// Driver Code
 
        let arr = [6, 8, 4, 5, 2, 3];
        let n = arr.length;
           
        document.write("Sum is "
                          + solve(arr, n));
 
</script>

Producción : 

Sum is 604

Método 2 (para números grandes) 

Cuando tenemos que lidiar con números muy grandes (como en la sección PRÁCTICA de esta pregunta), el enfoque anterior no funcionará. La idea básica de abordar la pregunta es la misma que la anterior, pero en lugar de usar números, usaremos strings para manejar la suma.

Para sumar dos números dados en forma de string, puede consultar this .

C++

#include <bits/stdc++.h>
using namespace std;
 
string solve(int arr[], int n)
{
    // code here
    // sorting of array O(nlogn)
    sort(arr, arr + n);
    // Two String for storing our two minimum numbers
    string a = "", b = "";
    // string string alternatively
    for (int i = 0; i < n; i += 2)
    {
        a += (arr[i] + '0');
    }
    for (int i = 1; i < n; i += 2)
    {
        b += (arr[i] + '0');
    }
    int j = a.length() - 1;
    int k = b.length() - 1;
    // as initial carry is zero
    int carry = 0;
    string ans = "";
    while (j >= 0 && k >= 0)
    {
        int sum = 0;
        sum += (a[j] - '0') + (b[k] - '0') + carry;
        ans += to_string(sum % 10);
        carry = sum / 10;
        j--;
        k--;
    }
    // if string b is over and string a is left
    // here we dont need to put here while condition
    // as it would run at max one time. Because the difference
    // between both the strings could be at max 1.
    while (j >= 0)
    {
        int sum = 0;
        sum += (a[j] - '0') + carry;
        ans += to_string(sum % 10);
        carry = sum / 10;
        j--;
    }
    // if string a is over and string b is left
    while (k >= 0)
    {
        int sum = 0;
        sum += (b[k] - '0') + carry;
        ans += to_string(sum % 10);
        carry = sum / 10;
        k--;
    }
    // if carry is left
    if (carry)
    {
        ans += to_string(carry);
    }
    // to remove leading zeroes as they will be ahead of our sum
    while (!ans.empty() and ans.back() == '0')
        ans.pop_back();
    // reverse our final string because we were storing sum from left to right
    reverse(ans.begin(), ans.end());
    return ans;
}
 
//  Driver Code Starts.
int main()
{
    int arr[] = {6, 8, 4, 5, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Sum is " << solve(arr, n);
    return 0;
} //  Driver Code Ends

Python3

# Python code for the approach
def solve(arr, n):
 
    # sorting of array O(nlogn)
    arr.sort()
     
    # Two String for storing our two minimum numbers
    a,b = "",""
     
    # string string alternatively
    for i in range(0,n,2):
        a += str(arr[i])
 
    for i in range(1,n,2):
        b += str(arr[i])
 
    j = len(a) - 1
    k = len(b) - 1
    # as initial carry is zero
    carry = 0
    ans = ""
    while (j >= 0 and k >= 0):
        sum = 0
        sum += (ord(a[j]) - ord('0') + ord(b[k]) - ord('0')) + carry
        ans += str(sum % 10)
        carry = sum // 10
        j -= 1
        k -= 1
         
    # if string b is over and string a is left
    # here we dont need to put here while condition
    # as it would run at max one time. Because the difference
    # between both the strings could be at max 1.
    while (j >= 0):
        sum = 0
        sum += (a[j] - '0') + carry
        ans += (sum % 10).toString()
        carry = sum // 10
        j -= 1
         
    # if string a is over and string b is left
    while (k >= 0):
        sum = 0
        sum += ord(b[k]) - ord('0') + carry
        ans += str(sum % 10)
        carry = (sum // 10)
        k -= 1
 
    # if carry is left
    if (carry):
        ans += str(carry)
     
    # to remove leading zeroes as they will be ahead of our sum
    while (len(ans) and ans[len(ans) - 1] == '0'):
        ans.pop()
         
    # reverse our final string because we were storing sum from left to right
    ans = ans[::-1]
    return ans
 
#  Driver Code
arr = [6, 8, 4, 5, 2, 3]
n = len(arr)
print("Sum is " + solve(arr, n))
 
# This code is contributed by shinjanpatra

Javascript

<script>
 
function solve(arr, n)
{
 
    // sorting of array O(nlogn)
    arr.sort();
     
    // Two String for storing our two minimum numbers
    let a = "", b = "";
     
    // string string alternatively
    for (let i = 0; i < n; i += 2)
    {
        a += arr[i];
    }
    for (let i = 1; i < n; i += 2)
    {
        b += arr[i];
    }
    let j = a.length - 1;
    let k = b.length - 1;
    // as initial carry is zero
    let carry = 0;
    let ans = "";
    while (j >= 0 && k >= 0)
    {
        let sum = 0;
        sum += (a.charCodeAt(j) - '0'.charCodeAt(0)) + (b.charCodeAt(k) - '0'.charCodeAt(0)) + carry;
        ans += (sum % 10).toString();
        carry = Math.floor(sum / 10);
        j--;
        k--;
    }
    // if string b is over and string a is left
    // here we dont need to put here while condition
    // as it would run at max one time. Because the difference
    // between both the strings could be at max 1.
    while (j >= 0)
    {
        let sum = 0;
        sum += (a[j] - '0') + carry;
        ans += (sum % 10).toString();
        carry = Math.floor(sum / 10);
        j--;
    }
    // if string a is over and string b is left
    while (k >= 0)
    {
        let sum = 0;
        sum += (b.charCodeAt(k) - '0'.charCodeAt(0)) + carry;
        ans += (sum % 10).toString();
        carry = Math.floor(sum / 10);
        k--;
    }
    // if carry is left
    if (carry)
    {
        ans += carry.toString();
    }
     
    // to remove leading zeroes as they will be ahead of our sum
    while (ans.length && ans[ans.length-1] == '0')
        ans.pop();
         
    // reverse our final string because we were storing sum from left to right
    ans = ans.split('').reverse().join('');
    return ans;
}
 
//  Driver Code Starts.
 
let arr = [6, 8, 4, 5, 2, 3];
let n = arr.length;
document.write("Sum is " + solve(arr, n));
 
// This code is contributed by shinjanpatra
</script>
Producción

Sum is 604

Este artículo es una contribución de Aditya Goel . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *