Dados dos números naturales N1 y N2 , la tarea es encontrar la suma máxima posible después de intercambiar un solo dígito entre ellos.
Ejemplos:
Entrada: N1 = 984788, N2 = 706
Salida: 988194
Explicación:
Intercambiando 4 de N1 con 7 de N2, obtenemos N1 = 987788 y N2 = 406
Suma = 988194Entrada: N1 = 9987, N2 = 123
Salida: 10740
Explicación:
Intercambiando 8 de N1 con 1 de N2, obtenemos N1 = 9917 y N2 = 823
Suma = 10740
Acercarse:
- Compare N1 y N2 y almacene los dígitos del mayor de los dos en la array arr1 y el del menor en arr2 respectivamente.
- Si ambos números tienen diferentes longitudes , encuentre el índice del elemento máximo en arr2 y el índice más significativo en arr1 , e intercámbielos para maximizar la suma.
- Si ambos números tienen la misma longitud ,
- Iterar las arrays arr1 y arr2 al mismo tiempo.
- Para cada dígito en el índice i en ambas arrays, encuentre la diferencia entre el dígito actual y el dígito más grande que queda para el índice ‘i’.
- Compare la diferencia para encontrar el dígito más significativo y el índice más significativo, cuyo valor debe intercambiarse.
- Restaure los nuevos números de arr1 y arr2 y calcule la suma maximizada.
El siguiente código es la implementación del enfoque anterior:
C++
// C++ program to maximise the sum of two
// Numbers using at most one swap between them
#include <bits/stdc++.h>
using namespace std;
#define MAX 100
// Function to maximize the sum
// by swapping only one digit
void findMaxSum(int n1, int n2)
{
int arr1[MAX] = { 0 }, arr2[MAX] = { 0 };
int l1 = 0, l2 = 0;
int max1 = max(n1, n2);
int min1 = min(n1, n2);
// Store digits of max(n1, n2)
for (int i = max1; i > 0; i /= 10)
arr1[l1++] = (i % 10);
// Store digits of min(n1, n2)
for (int i = min1; i > 0; i /= 10)
arr2[l2++] = (i % 10);
int f = 0;
// If length of the two numbers
// are unequal
if (l1 != l2) {
// Find the most significant number
// and the most significant index
// for swapping
int index = (max_element(arr2, arr2 + l2) - arr2);
for (int i = l1 - 1; i > (l2 - 1); i--) {
if (arr1[i] < arr2[index]) {
swap(arr1[i], arr2[index]);
f = 1;
break;
}
}
}
// If both numbers are
// of equal length
if (f != 1) {
int index1 = 0, index2 = 0;
int diff1 = 0, diff2 = 0;
for (int i = l2 - 1; i >= 0; i--) {
// Fetch the index of current maximum
// digit present in both the arrays
index1 = (max_element(arr1, arr1 + i) - arr1);
index2 = (max_element(arr2, arr2 + i) - arr2);
// Compute the difference
diff1 = (arr2[index2] - arr1[i]);
diff2 = (arr1[index1] - arr2[i]);
// Find the most significant index
// and the most significant digit
// to be swapped
if (diff1 > 0 || diff2 > 0) {
if (diff1 > diff2) {
swap(arr1[i], arr2[index2]);
break;
}
else if (diff2 > diff1) {
swap(arr2[i], arr1[index1]);
break;
}
else if (diff1 == diff2) {
if (index1 <= index2) {
swap(arr2[i], arr1[index1]);
break;
}
else if (index2 <= index1) {
swap(arr1[i], arr2[index2]);
break;
}
}
}
}
}
// Restore the new numbers
int f_n1 = 0, f_n2 = 0;
for (int i = l1 - 1; i >= 0; i--) {
f_n1 = (f_n1 * 10) + arr1[i];
f_n2 = (f_n2 * 10) + arr2[i];
}
// Display the maximized sum
cout << (f_n1 + f_n2) << "\n";
}
// Driver function
int main()
{
int N1 = 9987;
int N2 = 123;
findMaxSum(N1, N2);
return 0;
}
Java
// Java program to maximise the sum of two
// Numbers using at most one swap between them
import java.util.*;
class GFG{
static int MAX = 100;
static int max_element(int arr[], int pos)
{
int tmp = arr[0];
int ind = 0;
for(int i = 1; i < pos; i++)
{
if (tmp < arr[i])
{
tmp = arr[i];
ind = i;
}
}
return ind;
}
// Function to maximize the sum
// by swapping only one digit
static void findMaxSum(int n1, int n2)
{
int []arr1 = new int[MAX];
int []arr2 = new int[MAX];
int l1 = 0, l2 = 0;
int max1 = Math.max(n1, n2);
int min1 = Math.min(n1, n2);
// Store digits of max(n1, n2)
for(int i = max1; i > 0; i /= 10)
arr1[l1++] = (i % 10);
// Store digits of min(n1, n2)
for(int i = min1; i > 0; i /= 10)
arr2[l2++] = (i % 10);
int f = 0;
// If length of the two numbers
// are unequal
if (l1 != l2)
{
// Find the most significant number
// and the most significant index
// for swapping
int index = (max_element(arr2, l2));
for(int i = l1 - 1; i > (l2 - 1); i--)
{
if (arr1[i] < arr2[index])
{
int tmp = arr1[i];
arr1[i] = arr2[index];
arr2[index] = tmp;
f = 1;
break;
}
}
}
// If both numbers are
// of equal length
if (f != 1)
{
int index1 = 0, index2 = 0;
int diff1 = 0, diff2 = 0;
for(int i = l2 - 1; i >= 0; i--)
{
// Fetch the index of current maximum
// digit present in both the arrays
index1 = (max_element(arr1, i));
index2 = (max_element(arr2, i));
// Compute the difference
diff1 = (arr2[index2] - arr1[i]);
diff2 = (arr1[index1] - arr2[i]);
// Find the most significant index
// and the most significant digit
// to be swapped
if (diff1 > 0 || diff2 > 0)
{
if (diff1 > diff2)
{
int tmp = arr1[i];
arr1[i] = arr2[index2];
arr2[index2] = tmp;
break;
}
else if (diff2 > diff1)
{
int tmp = arr1[index1];
arr1[index1] = arr2[i];
arr2[i] = tmp;
break;
}
else if (diff1 == diff2)
{
if (index1 <= index2)
{
int tmp = arr1[index1];
arr1[index1] = arr2[i];
arr2[i] = tmp;
break;
}
else if (index2 <= index1)
{
int tmp = arr1[i];
arr1[i] = arr2[index2];
arr2[index2] = tmp;
break;
}
}
}
}
}
// Restore the new numbers
int f_n1 = 0, f_n2 = 0;
for(int i = l1 - 1; i >= 0; i--)
{
f_n1 = (f_n1 * 10) + arr1[i];
f_n2 = (f_n2 * 10) + arr2[i];
}
// Display the maximized sum
System.out.println(f_n1 + f_n2);
}
// Driver code
public static void main(String[] args)
{
int N1 = 9987;
int N2 = 123;
findMaxSum(N1, N2);
}
}
// This code is contributed by grand_master
Python3
# Python program to maximise the sum of two # Numbers using at most one swap between them MAX = 100 # Function to maximize the sum # by swapping only one digit def findMaxSum(n1, n2): arr1 = [0]*(MAX) arr2 = [0]*(MAX) l1 = 0 l2 = 0 max1 = max(n1, n2); min1 = min(n1, n2); # Store digits of max(n1, n2) i = max1 while i > 0: arr1[l1] = (i % 10) l1 += 1 i //= 10 # Store digits of min(n1, n2) i = min1 while i > 0: arr2[l2] = (i % 10) l2 += 1 i //= 10 f = 0 # If length of the two numbers # are unequal if (l1 != l2): # Find the most significant number # and the most significant index # for swapping index = arr2.index(max(arr2)) for i in range ( l1 - 1, (l2 - 1), -1): if (arr1[i] < arr2[index]): (arr1[i], arr2[index]) = (arr2[index],arr1[i]) f = 1 break # If both numbers are # of equal length if (f != 1): index1 = 0 index2 = 0 diff1 = 0 diff2 = 0 for i in range( l2 - 1, -1,-1): # Fetch the index of current maximum # digit present in both the arrays index1 = arr1.index(max(arr1[:i])) index2 = arr2.index(max(arr2[:i])) # Compute the difference diff1 = (arr2[index2] - arr1[i]); diff2 = (arr1[index1] - arr2[i]); # Find the most significant index # and the most significant digit # to be swapped if (diff1 > 0 or diff2 > 0): if (diff1 > diff2): arr1[i], arr2[index2] = arr2[index2],arr1[i] break elif (diff2 > diff1): arr2[i], arr1[index1] = arr1[index1],arr2[i] break elif (diff1 == diff2): if (index1 <= index2): arr2[i], arr1[index1] = arr1[index1],arr2[i] break elif (index2 <= index1): arr1[i], arr2[index2] = arr2[index2],arr1[i] break; # Restore the new numbers f_n1 = 0 f_n2 = 0 for i in range (l1 - 1, -1,-1): f_n1 = (f_n1 * 10) + arr1[i] f_n2 = (f_n2 * 10) + arr2[i] # Display the maximized sum print(f_n1 + f_n2) # Driver function N1 = 9987 N2 = 123 findMaxSum(N1, N2) # This code is contributed by ANKITKUMAR34
C#
// C# program to maximise the sum of two
// Numbers using at most one swap between them
using System;
class GFG{
static int MAX = 100;
static int max_element(int []arr, int pos)
{
int tmp = arr[0];
int ind = 0;
for(int i = 1; i < pos; i++)
{
if (tmp < arr[i])
{
tmp = arr[i];
ind = i;
}
}
return ind;
}
// Function to maximize the sum
// by swapping only one digit
static void findMaxSum(int n1, int n2)
{
int []arr1 = new int[MAX];
int []arr2 = new int[MAX];
int l1 = 0, l2 = 0;
int max1 = Math.Max(n1, n2);
int min1 = Math.Min(n1, n2);
// Store digits of max(n1, n2)
for(int i = max1; i > 0; i /= 10)
arr1[l1++] = (i % 10);
// Store digits of min(n1, n2)
for(int i = min1; i > 0; i /= 10)
arr2[l2++] = (i % 10);
int f = 0;
// If length of the two numbers
// are unequal
if (l1 != l2)
{
// Find the most significant number
// and the most significant index
// for swapping
int index = (max_element(arr2,l2));
for(int i = l1 - 1; i > (l2 - 1); i--)
{
if (arr1[i] < arr2[index])
{
int tmp = arr1[i];
arr1[i] = arr2[index];
arr2[index] = tmp;
f = 1;
break;
}
}
}
// If both numbers are
// of equal length
if (f != 1)
{
int index1 = 0, index2 = 0;
int diff1 = 0, diff2 = 0;
for(int i = l2 - 1; i >= 0; i--)
{
// Fetch the index of current maximum
// digit present in both the arrays
index1 = (max_element(arr1, i));
index2 = (max_element(arr2, i));
// Compute the difference
diff1 = (arr2[index2] - arr1[i]);
diff2 = (arr1[index1] - arr2[i]);
// Find the most significant index
// and the most significant digit
// to be swapped
if (diff1 > 0 || diff2 > 0)
{
if (diff1 > diff2)
{
int tmp = arr1[i];
arr1[i] = arr2[index2];
arr2[index2] = tmp;
break;
}
else if (diff2 > diff1)
{
int tmp = arr1[index1];
arr1[index1] = arr2[i];
arr2[i] = tmp;
break;
}
else if (diff1 == diff2)
{
if (index1 <= index2)
{
int tmp = arr1[index1];
arr1[index1] = arr2[i];
arr2[i] = tmp;
break;
}
else if (index2 <= index1)
{
int tmp = arr1[i];
arr1[i] = arr2[index2];
arr2[index2] = tmp;
break;
}
}
}
}
}
// Restore the new numbers
int f_n1 = 0, f_n2 = 0;
for(int i = l1 - 1; i >= 0; i--)
{
f_n1 = (f_n1 * 10) + arr1[i];
f_n2 = (f_n2 * 10) + arr2[i];
}
// Display the maximized sum
Console.Write(f_n1 + f_n2);
}
// Driver code
public static void Main(string[] args)
{
int N1 = 9987;
int N2 = 123;
findMaxSum(N1, N2);
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// JavaScript program to maximise the sum of two
// Numbers using at most one swap between them
let MAX = 100;
function max_element(arr, pos)
{
let tmp = arr[0];
let ind = 0;
for(let i = 1; i < pos; i++)
{
if (tmp < arr[i])
{
tmp = arr[i];
ind = i;
}
}
return ind;
}
// Function to maximize the sum
// by swapping only one digit
function findMaxSum(n1, n2)
{
let arr1 = Array.from({length: MAX}, (_, i) => 0);
let arr2 = Array.from({length: MAX}, (_, i) => 0);
let l1 = 0, l2 = 0;
let max1 = Math.max(n1, n2);
let min1 = Math.min(n1, n2);
// Store digits of max(n1, n2)
for(let i = max1; i > 0; i = Math.floor(i / 10))
arr1[l1++] = (i % 10);
// Store digits of min(n1, n2)
for(let i = min1; i > 0; i = Math.floor(i / 10))
arr2[l2++] = (i % 10);
let f = 0;
// If length of the two numbers
// are unequal
if (l1 != l2)
{
// Find the most significant number
// and the most significant index
// for swapping
let index = (max_element(arr2, l2));
for(let i = l1 - 1; i > (l2 - 1); i--)
{
if (arr1[i] < arr2[index])
{
let tmp = arr1[i];
arr1[i] = arr2[index];
arr2[index] = tmp;
f = 1;
break;
}
}
}
// If both numbers are
// of equal length
if (f != 1)
{
let index1 = 0, index2 = 0;
let diff1 = 0, diff2 = 0;
for(let i = l2 - 1; i >= 0; i--)
{
// Fetch the index of current maximum
// digit present in both the arrays
index1 = (max_element(arr1, i));
index2 = (max_element(arr2, i));
// Compute the difference
diff1 = (arr2[index2] - arr1[i]);
diff2 = (arr1[index1] - arr2[i]);
// Find the most significant index
// and the most significant digit
// to be swapped
if (diff1 > 0 || diff2 > 0)
{
if (diff1 > diff2)
{
let tmp = arr1[i];
arr1[i] = arr2[index2];
arr2[index2] = tmp;
break;
}
else if (diff2 > diff1)
{
let tmp = arr1[index1];
arr1[index1] = arr2[i];
arr2[i] = tmp;
break;
}
else if (diff1 == diff2)
{
if (index1 <= index2)
{
let tmp = arr1[index1];
arr1[index1] = arr2[i];
arr2[i] = tmp;
break;
}
else if (index2 <= index1)
{
let tmp = arr1[i];
arr1[i] = arr2[index2];
arr2[index2] = tmp;
break;
}
}
}
}
}
// Restore the new numbers
let f_n1 = 0, f_n2 = 0;
for(let i = l1 - 1; i >= 0; i--)
{
f_n1 = (f_n1 * 10) + arr1[i];
f_n2 = (f_n2 * 10) + arr2[i];
}
// Display the maximized sum
document.write(f_n1 + f_n2);
}
// Driver Code
let N1 = 9987;
let N2 = 123;
findMaxSum(N1, N2);
</script>
Producción:
10740
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(MAX)
Publicación traducida automáticamente
Artículo escrito por epistler_999 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA