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:
Entrada: arr[] = {6, 8, 4, 5, 2, 3}
Salida: 604
246 + 358 = 604
Entrada: arr[] = {5, 3, 0, 7, 4}
Salida: 82
Enfoque: Se formará un número mínimo a partir del conjunto de dígitos cuando el dígito más pequeño aparezca en la posición más significativa y el próximo dígito más pequeño aparezca en la siguiente posición más significativa y así sucesivamente…
La idea es construir dos números alternando la selección de dígitos del array (suponiendo que esté ordenado de forma ascendente). 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. Para reducir la complejidad del tiempo, la array se puede ordenar en O(n) utilizando la array de frecuencia de dígitos, ya que cada elemento de la array original es un solo dígito, es decir, puede haber como máximo 10 elementos distintos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach
#include<bits/stdc++.h>
using namespace std;
// Function to return the required minimum sum
int minSum(vector<int> arr, int n)
{
// Array to store the
// frequency of each digit
int MAX = 10;
int *freq = new int[MAX];
for (int i = 0; i < n; i++) {
// Store count of every digit
freq[arr[i]]++;
}
// Update arr[] such that it is
// sorted in ascending
int k = 0;
for (int i = 0; i < MAX; i++) {
// Adding elements in arr[]
// in sorted order
for (int j = 0; j < freq[i]; j++) {
arr[k++] = i;
}
}
int num1 = 0;
int num2 = 0;
// Generating numbers alternatively
for (int i = 0; i < n; i++) {
if (i % 2 == 0)
num1 = num1 * MAX + arr[i];
else
num2 = num2 * MAX + arr[i];
}
// Return the minimum possible sum
return num1 + num2;
}
// Driver code
int main(void)
{
vector<int>arr = { 6, 8, 4, 5, 2, 3 };
int n = arr.size();
cout << minSum(arr, n);
}
// This code is contributed by ankush_953
Java
// Java implementation of above approach
public class GFG {
public static final int MAX = 10;
// Function to return the required minimum sum
static int minSum(int arr[], int n)
{
// Array to store the
// frequency of each digit
int freq[] = new int[MAX];
for (int i = 0; i < n; i++) {
// Store count of every digit
freq[arr[i]]++;
}
// Update arr[] such that it is
// sorted in ascending
int k = 0;
for (int i = 0; i < MAX; i++) {
// Adding elements in arr[]
// in sorted order
for (int j = 0; j < freq[i]; j++) {
arr[k++] = i;
}
}
int num1 = 0;
int num2 = 0;
// Generating numbers alternatively
for (int i = 0; i < n; i++) {
if (i % 2 == 0)
num1 = num1 * MAX + arr[i];
else
num2 = num2 * MAX + arr[i];
}
// Return the minimum possible sum
return num1 + num2;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 6, 8, 4, 5, 2, 3 };
int n = arr.length;
System.out.print(minSum(arr, n));
}
}
Python3
# Python implementation of above approach # Function to return the required minimum sum def minSum(arr, n): # Array to store the # frequency of each digit MAX = 10 freq = [0]*MAX for i in range(n): # Store count of every digit freq[arr[i]] += 1 # Update arr[] such that it is # sorted in ascending k = 0 for i in range(MAX): # Adding elements in arr[] # in sorted order for j in range(0,freq[i]): arr[k] = i k += 1 num1 = 0 num2 = 0 # Generating numbers alternatively for i in range(n): if i % 2 == 0: num1 = num1 * MAX + arr[i] else: num2 = num2 * MAX + arr[i] # Return the minimum possible sum return num1 + num2 # Driver code arr = [ 6, 8, 4, 5, 2, 3 ] n = len(arr); print(minSum(arr, n)) #This code is contributed by ankush_953
C#
// C# implementation of above approach
using System;
class GFG {
public static int MAX = 10;
// Function to return the required minimum sum
static int minSum(int[] arr, int n)
{
// Array to store the
// frequency of each digit
int[] freq = new int[MAX];
for (int i = 0; i < n; i++) {
// Store count of every digit
freq[arr[i]]++;
}
// Update arr[] such that it is
// sorted in ascending
int k = 0;
for (int i = 0; i < MAX; i++) {
// Adding elements in arr[]
// in sorted order
for (int j = 0; j < freq[i]; j++) {
arr[k++] = i;
}
}
int num1 = 0;
int num2 = 0;
// Generating numbers alternatively
for (int i = 0; i < n; i++) {
if (i % 2 == 0)
num1 = num1 * MAX + arr[i];
else
num2 = num2 * MAX + arr[i];
}
// Return the minimum possible sum
return num1 + num2;
}
// Driver code
static public void Main()
{
int[] arr = { 6, 8, 4, 5, 2, 3 };
int n = arr.Length;
Console.WriteLine(minSum(arr, n));
}
}
// This code is contributed by jit_t.
Javascript
<script>
// Javascript implementation of above approach
let MAX = 10;
// Function to return the required minimum sum
function minSum(arr, n)
{
// Array to store the
// frequency of each digit
let freq = new Array(MAX);
freq.fill(0);
for (let i = 0; i < n; i++) {
// Store count of every digit
freq[arr[i]]++;
}
// Update arr[] such that it is
// sorted in ascending
let k = 0;
for (let i = 0; i < MAX; i++) {
// Adding elements in arr[]
// in sorted order
for (let j = 0; j < freq[i]; j++) {
arr[k++] = i;
}
}
let num1 = 0;
let num2 = 0;
// Generating numbers alternatively
for (let i = 0; i < n; i++) {
if (i % 2 == 0)
num1 = num1 * MAX + arr[i];
else
num2 = num2 * MAX + arr[i];
}
// Return the minimum possible sum
return num1 + num2;
}
let arr = [ 6, 8, 4, 5, 2, 3 ];
let n = arr.length;
document.write(minSum(arr, n));
</script>
604
Complejidad de tiempo: O(n)
Publicación traducida automáticamente
Artículo escrito por Rajat Gaur 1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA