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
Como queremos minimizar la suma de dos números que se van a formar, debemos dividir todos los dígitos en dos mitades y asignarles mitades de dígitos. También debemos asegurarnos de que los primeros dígitos sean más pequeños.
Construimos un Min Heap con los elementos de la array dada, que toma O (n) peor tiempo. Ahora recuperamos los valores mínimos (2 a la vez) de la array, sondeando desde la cola de prioridad y agregamos estos dos valores mínimos a nuestros números, hasta que el montón se vacía, es decir, todos los elementos de la array se agotan. Devolvemos la suma de dos números formados, que es nuestra respuesta requerida. La complejidad general es O(nlogn) ya que la operación push() toma O(logn) y se repite n veces.
Implementación:
C++
// C++ program to find minimum sum of two numbers
// formed from all digits in a given array.
#include<bits/stdc++.h>
using namespace std;
// Returns sum of two numbers formed
// from all digits in a[]
int minSum(int arr[], int n)
{
// min Heap
priority_queue <int, vector<int>, greater<int> > pq;
// to store the 2 numbers formed by array elements to
// minimize the required sum
string num1, num2;
// Adding elements in Priority Queue
for(int i=0; i<n; i++)
pq.push(arr[i]);
// checking if the priority queue is non empty
while(!pq.empty())
{
// appending top of the queue to the string
num1+=(48 + pq.top());
pq.pop();
if(!pq.empty())
{
num2+=(48 + pq.top());
pq.pop();
}
}
// converting string to integer
int a = atoi(num1.c_str());
int b = atoi(num2.c_str());
// returning the sum
return a+b;
}
int main()
{
int arr[] = {6, 8, 4, 5, 2, 3};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<minSum(arr, n)<<endl;
return 0;
}
// Contributed By: Harshit Sidhwa
Java
// Java program to find minimum sum of two numbers
// formed from all digits in a given array.
import java.util.PriorityQueue;
class MinSum
{
// Returns sum of two numbers formed
// from all digits in a[]
public static long solve(int[] a)
{
// min Heap
PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
// to store the 2 numbers formed by array elements to
// minimize the required sum
StringBuilder num1 = new StringBuilder();
StringBuilder num2 = new StringBuilder();
// Adding elements in Priority Queue
for (int x : a)
pq.add(x);
// checking if the priority queue is non empty
while (!pq.isEmpty())
{
num1.append(pq.poll()+ "");
if (!pq.isEmpty())
num2.append(pq.poll()+ "");
}
// the required sum calculated
long sum = Long.parseLong(num1.toString()) +
Long.parseLong(num2.toString());
return sum;
}
// Driver code
public static void main (String[] args)
{
int arr[] = {6, 8, 4, 5, 2, 3};
System.out.println("The required sum is "+ solve(arr));
}
}
Python3
# Python3 program to find minimum
# sum of two numbers formed from
# all digits in a given array.
from queue import PriorityQueue
# Returns sum of two numbers formed
# from all digits in a[]
def solve(a):
# min Heap
pq = PriorityQueue()
# To store the 2 numbers
# formed by array elements to
# minimize the required sum
num1 = ""
num2 = ""
# Adding elements in
# Priority Queue
for x in a:
pq.put(x)
# Checking if the priority
# queue is non empty
while not pq.empty():
num1 += str(pq.get())
if not pq.empty():
num2 += str(pq.get())
# The required sum calculated
sum = int(num1) + int(num2)
return sum
# Driver code
if __name__=="__main__":
arr = [ 6, 8, 4, 5, 2, 3 ]
print("The required sum is ", solve(arr))
# This code is contributed by rutvik_56
C#
// C# program to find minimum sum of two numbers
// formed from all digits in a given array.
using System;
using System.Collections.Generic;
class GFG
{
// Returns sum of two numbers formed
// from all digits in a[]
public static long solve(int[] a)
{
// min Heap
List<int> pq = new List<int>();
// to store the 2 numbers formed by array elements to
// minimize the required sum
string num1 = "";
string num2 = "";
// Adding elements in Priority Queue
foreach(int x in a)
pq.Add(x);
pq.Sort();
// checking if the priority queue is non empty
while (pq.Count > 0)
{
num1 = num1 + pq[0];
pq.RemoveAt(0);
if (pq.Count > 0)
{
num2 = num2 + pq[0];
pq.RemoveAt(0);
}
}
// the required sum calculated
int sum = Int32.Parse(num1) + Int32.Parse(num2);
return sum;
}
// Driver code
static void Main()
{
int[] arr = {6, 8, 4, 5, 2, 3};
Console.WriteLine("The required sum is "+ solve(arr));
}
}
// This code is contributed by divyesh072019.
Javascript
<script>
// Javascript program to find minimum sum of two numbers
// formed from all digits in a given array.
// Returns sum of two numbers formed
// from all digits in a[]
function solve(a)
{
// min Heap
pq=[];
// to store the 2 numbers formed by array elements to
// minimize the required sum
let num1="";
let num2="";
// Adding elements in Priority Queue
for(let x=0;x<a.length;x++)
{
pq.push(a[x]);
}
pq.sort(function(a,b){return b-a;});
// checking if the priority queue is non empty
while(pq.length!=0)
{
num1+=pq.pop();
if(pq.length!=0)
{
num2+=pq.pop();
}
}
// the required sum calculated
let sum=parseInt(num1)+parseInt(num2);
return sum;
}
// Driver code
let arr=[6, 8, 4, 5, 2, 3];
document.write("The required sum is "+ solve(arr));
// This code is contributed by avanitrachhadiya2155
</script>
604
Otro método: podemos seguir otro enfoque también como este, ya que necesitamos dos números tales que su suma sea mínima, entonces también necesitaríamos dos números mínimos. Si organizamos nuestra array en orden ascendente, podemos obtener dos dígitos que formarán los números más pequeños,
por ejemplo, 2 3 4 5 6 8, ahora podemos obtener dos números a partir de 2 y 3. La primera parte ya está hecha. Avanzando, tenemos que formar de tal manera que contengan dígitos pequeños, es decir, elegir dígitos alternativamente de una array y extender sus dos números.
es decir, 246, 358. Ahora, si analizamos esto, podemos elegir números pares indexados para num1 y un número impar para num2.
A continuación se muestra la implementación:
C++
// C++ program to find minimum sum of two numbers
// formed from all digits in a given array.
#include <bits/stdc++.h>
using namespace std;
// Returns sum of two numbers formed
// from all digits in a[]
int minSum(int a[], int n)
{
// sort the elements
sort(a, a + n);
int num1 = 0;
int num2 = 0;
for (int i = 0; i < n; i++) {
if (i % 2 == 0)
num1 = num1 * 10 + a[i];
else
num2 = num2 * 10 + a[i];
}
return num2 + num1;
}
// Driver code
int main()
{
int arr[] = { 5, 3, 0, 7, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "The required sum is " << minSum(arr, n)
<< endl;
return 0;
}
// This code is contributed by Sania Kumari Gupta
C
// C program to find minimum sum of two numbers
// formed from all digits in a given array.
#include <stdio.h>
#include <stdlib.h>
int cmpfunc(const void* a, const void* b)
{
return (*(int*)a - *(int*)b);
}
// Returns sum of two numbers formed
// from all digits in a[]
int minSum(int a[], int n)
{
// sort the elements
qsort(a, n, sizeof(int), cmpfunc);
// sort(a,a+n);
int num1 = 0;
int num2 = 0;
for (int i = 0; i < n; i++) {
if (i % 2 == 0)
num1 = num1 * 10 + a[i];
else
num2 = num2 * 10 + a[i];
}
return num2 + num1;
}
// Driver code
int main()
{
int arr[] = { 5, 3, 0, 7, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("The required sum is %d", minSum(arr, n));
return 0;
}
// This code is contributed by Sania Kumari Gupta
Java
import java.util.Arrays;
// Java program to find minimum sum of two numbers
// formed from all digits in a given array.
public class AQRQ {
// Returns sum of two numbers formed
// from all digits in a[]
static int minSum(int a[], int n)
{
// sort the elements
Arrays.sort(a);
int num1 = 0;
int num2 = 0;
for (int i = 0; i < n; i++) {
if (i % 2 == 0)
num1 = num1 * 10 + a[i];
else
num2 = num2 * 10 + a[i];
}
return num2 + num1;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 5, 3, 0, 7, 4 };
int n = arr.length;
System.out.println("The required sum is "
+ minSum(arr, n));
}
}
// This code is contributed by Sania Kumari Gupta
Python3
# Python 3 program to find minimum
# sum of two numbers formed
# from all digits in an given array
# Returns sum of two numbers formed
# from all digits in a[]
def minSum(a, n):
# sorted the elements
a = sorted(a)
num1, num2 = 0, 0
for i in range(n):
if i % 2 == 0:
num1 = num1 * 10 + a[i]
else:
num2 = num2 * 10 + a[i]
return num2 + num1
# Driver code
arr = [5, 3, 0, 7, 4]
n = len(arr)
print("The required sum is",
minSum(arr, n))
# This code is contributed
# by Mohit kumar 29
C#
// C# a program to find minimum sum of two numbers
//formed from all digits in a given array.
using System;
public class GFG{
//Returns sum of two numbers formed
//from all digits in a[]
static int minSum(int []a, int n){
// sort the elements
Array.Sort(a);
int num1 = 0;
int num2 = 0;
for(int i = 0;i<n;i++){
if(i%2==0)
num1 = num1*10+a[i];
else num2 = num2*10+a[i];
}
return num2+num1;
}
//Driver code
static public void Main (){
int []arr = {5, 3, 0, 7, 4};
int n = arr.Length;
Console.WriteLine("The required sum is " + minSum(arr, n));
}
//This code is contributed by ajit.
}
PHP
<?php
// PHP program to find minimum sum
// of two numbers formed from all
// digits in a given array.
// Returns sum of two numbers formed
// from all digits in a[]
function minSum($a, $n)
{
// sort the elements
sort($a);
$num1 = 0;
$num2 = 0;
for($i = 0; $i < $n; $i++)
{
if($i % 2 == 0)
$num1 = $num1 * 10 + $a[$i];
else $num2 = $num2 * 10 + $a[$i];
}
return ($num2 + $num1);
}
// Driver code
$arr = array(5, 3, 0, 7, 4);
$n = sizeof($arr);
echo "The required sum is ",
minSum($arr, $n), "\n";
// This Code is Contributed by ajit
?>
Javascript
<script>
// JavaScript program to find minimum sum of two numbers
// formed from all digits in a given array.
// Returns sum of two numbers formed
// from all digits in a[]
function minSum(a, n){
// sort the elements
a.sort();
let num1 = 0;
let num2 = 0;
for(let i = 0;i<n;i++){
if(i%2==0)
num1 = num1*10+a[i];
else num2 = num2*10+a[i];
}
return num2+num1;
}
let arr = [5, 3, 0, 7, 4];
let n = arr.length;
document.write("The required sum is " + minSum(arr, n));
</script>
The required sum is 82
Complejidad de tiempo: O (nLogN)
Este artículo es una contribución de Prakhar . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo 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.
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