Maximice la suma de arrays concatenando los elementos correspondientes de dos arrays dadas

Posted on by Rudeus Greyrat

Dadas dos arrays A[] y B[] de la misma longitud, la tarea es encontrar la suma máxima de arrays que se puede formar uniendo los elementos correspondientes de la array en cualquier orden.
 

Entrada: A[] = {1, 2, 3, 4, 5}, B[] = {3, 2, 1, 4, 5} 
Salida: 183 
Explicación: 
Los números formados al unir los dígitos de los elementos son – 
Unir (A[0], B[0]) = Unir(1, 3) = 13 o 31 
Unirse(A[1], B[1]) = Unirse(2, 2) = 22 
Unirse(A[2], B[2]) = Unir(3, 1) = 31 o 13 
Unirse(A[3], B[3]) = Unirse(4, 4) = 44 
Unirse(A[4], B[4]) = Join(5, 5) = 55 
Por lo tanto, para la suma máxima, la array será {31, 22, 31, 44, 55} con suma = 183
Entrada: A[] = {11, 23, 38, 43, 59}, B[] = {36, 24, 17, 40, 56} 
Salida: 19850 
Explicación: 
Los números formados al unir los dígitos de los elementos son – 
Join(A[0], B[0]) = Join(11, 36) = 1136 o 3611 
Unirse(A[1], B[1]) = Unirse(23, 24) = 2324 o 2423 
Unirse(A[2], B[2]) = Unirse(38, 17) = 3817 o 1738 
Unirse(A[ 3], B[3]) = Join(43, 40) = 4340 o 4043 
Join(A[4], B[4]) = Join(59, 56) = 5956 o 5659 
Por lo tanto, para la suma máxima, la array ser {3611, 2423, 3817, 4340, 5956} con suma = 19850 
 

Enfoque: la idea es iterar sobre la array y para cada elemento correspondiente de la array 
 

  1. únelos iterando sobre los dígitos de un número y agrega los dígitos en otro número que se puede definir de la siguiente manera: 
     
// Join the numbers
for digits in numberA:
    numberB = numberB*10 + digit
  1.  
  2. Del mismo modo, une los números en orden inverso y toma el máximo de esos números.
  3. Actualice el elemento correspondiente de la array resultante con el máximo entre los dos.
  4. De manera similar, encuentre todos los elementos de la array resultante y calcule la suma.

A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ implementation to find the
// maximum array sum by concatenating
// corresponding elements of given two arrays
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to join the two numbers
int joinNumbers(int numA, int numB)
{
    int revB = 0;
 
    // Loop to reverse the digits
    // of the one number
    while (numB > 0) {
        revB = revB * 10 + (numB % 10);
        numB = numB / 10;
    }
 
    // Loop to join two numbers
    while (revB > 0) {
        numA = numA * 10 + (revB % 10);
        revB = revB / 10;
    }
    return numA;
}
 
// Function to find the maximum array sum
int findMaxSum(int A[], int B[], int n)
{
    int maxArr[n];
 
    // Loop to iterate over the two
    // elements of the array
    for (int i = 0; i < n; ++i) {
 
        int X = joinNumbers(A[i], B[i]);
        int Y = joinNumbers(B[i], A[i]);
        int mx = max(X, Y);
        maxArr[i] = mx;
    }
 
    // Find the array sum
    int maxAns = 0;
    for (int i = 0; i < n; i++) {
        maxAns += maxArr[i];
    }
 
    // Return the array sum
    return maxAns;
}
 
// Driver Code
int main()
{
    int N = 5;
    int A[5] = { 11, 23, 38, 43, 59 };
    int B[5] = { 36, 24, 17, 40, 56 };
 
    cout << findMaxSum(A, B, N);
}

Java

// Java implementation to find the
// maximum array sum by concatenating
// corresponding elements of given two arrays
class GFG {
 
// Function to join the two numbers
static int joinNumbers(int numA, int numB)
{
    int revB = 0;
 
    // Loop to reverse the digits
    // of the one number
    while (numB > 0)
    {
        revB = revB * 10 + (numB % 10);
        numB = numB / 10;
    }
 
    // Loop to join two numbers
    while (revB > 0)
    {
        numA = numA * 10 + (revB % 10);
        revB = revB / 10;
    }
 
    return numA;
}
 
// Function to find the maximum array sum
static int findMaxSum(int A[], int B[], int n)
{
    int maxArr[] = new int[n];
 
    // Loop to iterate over the two
    // elements of the array
    for(int i = 0; i < n; ++i)
    {
       int X = joinNumbers(A[i], B[i]);
       int Y = joinNumbers(B[i], A[i]);
       int mx = Math.max(X, Y);
 
       maxArr[i] = mx;
    }
 
    // Find the array sum
    int maxAns = 0;
    for(int i = 0; i < n; i++)
    {
       maxAns += maxArr[i];
    }
 
    // Return the array sum
    return maxAns;
}
 
// Driver Code
public static void main(String args[])
{
    int N = 5;
    int A[] = { 11, 23, 38, 43, 59 };
    int B[] = { 36, 24, 17, 40, 56 };
 
    System.out.println(findMaxSum(A, B, N));
}
}
 
// This code is contributed by rutvik_56   

Python3

# Python3 implementation to find the
# maximum array sum by concatenating
# corresponding elements of given two arrays
 
# Function to join the two numbers
def joinNumbers(numA, numB):
    revB = 0
 
    # Loop to reverse the digits
    # of the one number
    while (numB > 0):
        revB = revB * 10 + (numB % 10)
        numB = numB // 10
 
    # Loop to join two numbers
    while (revB > 0):
        numA = numA * 10 + (revB % 10)
        revB = revB // 10
 
    return numA
 
# Function to find the maximum array sum
def findMaxSum(A, B, n):
    maxArr = [0 for i in range(n)]
 
    # Loop to iterate over the two
    # elements of the array
    for i in range(n):
         
        X = joinNumbers(A[i], B[i])
        Y = joinNumbers(B[i], A[i])
        mx = max(X, Y)
        maxArr[i] = mx
 
    # Find the array sum
    maxAns = 0
     
    for i in range(n):
        maxAns += maxArr[i]
 
    # Return the array sum
    return maxAns
 
# Driver Code
if __name__ == '__main__':
     
    N = 5
    A = [ 11, 23, 38, 43, 59 ]
    B = [ 36, 24, 17, 40, 56 ]
 
    print(findMaxSum(A, B, N))
 
# This code is contributed by Samarth

C#

// C# implementation to find the
// maximum array sum by concatenating
// corresponding elements of given two arrays
using System;
class GFG{
 
// Function to join the two numbers
static int joinNumbers(int numA, int numB)
{
    int revB = 0;
 
    // Loop to reverse the digits
    // of the one number
    while (numB > 0)
    {
        revB = revB * 10 + (numB % 10);
        numB = numB / 10;
    }
 
    // Loop to join two numbers
    while (revB > 0)
    {
        numA = numA * 10 + (revB % 10);
        revB = revB / 10;
    }
 
    return numA;
}
 
// Function to find the maximum array sum
static int findMaxSum(int []A, int []B, int n)
{
    int []maxArr = new int[n];
 
    // Loop to iterate over the two
    // elements of the array
    for(int i = 0; i < n; ++i)
    {
        int X = joinNumbers(A[i], B[i]);
        int Y = joinNumbers(B[i], A[i]);
        int mx = Math.Max(X, Y);
     
        maxArr[i] = mx;
    }
 
    // Find the array sum
    int maxAns = 0;
    for(int i = 0; i < n; i++)
    {
        maxAns += maxArr[i];
    }
 
    // Return the array sum
    return maxAns;
}
 
// Driver Code
public static void Main(String []args)
{
    int N = 5;
    int []A = { 11, 23, 38, 43, 59 };
    int []B = { 36, 24, 17, 40, 56 };
 
    Console.WriteLine(findMaxSum(A, B, N));
}
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
 
// Javascript implementation to find the
// maximum array sum by concatenating
// corresponding elements of given two arrays
 
// Function to join the two numbers
function joinNumbers(numA, numB)
{
    var revB = 0;
 
    // Loop to reverse the digits
    // of the one number
    while (numB > 0) {
        revB = revB * 10 + (numB % 10);
        numB = parseInt(numB / 10);
    }
 
    // Loop to join two numbers
    while (revB > 0) {
        numA = numA * 10 + (revB % 10);
        revB = parseInt( revB / 10);
    }
    return numA;
}
 
// Function to find the maximum array sum
function findMaxSum(A, B, n)
{
    var maxArr = Array(n).fill(0);
 
    // Loop to iterate over the two
    // elements of the array
    for (var i = 0; i < n; ++i) {
 
        var X = joinNumbers(A[i], B[i]);
        var Y = joinNumbers(B[i], A[i]);
        var mx = Math.max(X, Y);
        maxArr[i] = mx;
    }
 
    // Find the array sum
    var maxAns = 0;
    for (var i = 0; i < n; i++) {
        maxAns += maxArr[i];
    }
 
    // Return the array sum
    return maxAns;
}
 
// Driver Code
var N = 5;
var A = [ 11, 23, 38, 43, 59 ];
var B = [ 36, 24, 17, 40, 56 ];
document.write( findMaxSum(A, B, N));
 
</script>
Producción: 

19850

 

Complejidad de Tiempo: O(n * (log 10 numB + log 10 revB))
Espacio Auxiliar: O(n)

Publicación traducida automáticamente

Artículo escrito por spp____ 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 *