Maximice la suma de la array eliminando repetidamente un elemento de pares cuya concatenación es un múltiplo de 3

Dada una array arr[] que consta de N enteros positivos, la tarea es encontrar la suma máxima posible de los elementos restantes de la array después de eliminar repetidamente cualquiera de los dos elementos cuya concatenación es un múltiplo de 3 .

Ejemplos:

Entrada: arr[] = {23, 12, 43, 3, 56}
Salida: 91
Explicación:
Inicialmente, la array es {23, 12, 43, 3, 56}. Se realizan las siguientes eliminaciones de los elementos de la array:

• Par {23, 43}: Concatenación = 2343, que es divisible por 3. Ahora, eliminar 43 modifica la array a {23, 12, 3, 56}.
• Par {12, 3}: Concatenación = 123, que es divisible por 3. Ahora, eliminar 3 modifica la array a {23, 12, 56}.

Después de las operaciones anteriores, la suma de los elementos del arreglo = 12 + 56 + 23 = 91.

Entrada: arr[] = {324, 32, 53, 67, 330}
Salida: 415

Enfoque: El problema dado se puede resolver usando el hecho de que el resto de un número, cuando se divide por 3 , es igual al resto de la suma de sus dígitos cuando se divide por 3. Siga los pasos a continuación para resolver el problema:

• Inicialice tres variables, digamos maxRem0 , maxRem1 y maxRem2 , para almacenar el elemento cuyo resto sea 0 , 1 y 2 respectivamente.
• Recorra la array dada arr[] y realice los siguientes pasos:
  • Inicialice una variable, digitSum para almacenar la suma de dígitos.
  • Si digitSum % 3 == 0 , actualice el valor de maxRem0 como max(maxRem0, arr[i]) .
  • De lo contrario, si el resto es 1 o 2 , entonces
• Después de completar los pasos anteriores, imprima la suma de maxRem0 y el valor máximo de maxRem1 y maxRem2 como resultado.

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

// C++ approach for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate sum
// of digits of an integer
int getSum(int n)
{
    int ans = 0;
     
    // char[] arr = (String.valueOf(n)).toCharArray();
    string arr = to_string(n);
    for(int i = 0; i < arr.length(); i++)
    {
        ans += int(arr[i]);
    }
    return ans;
}
 
// Function to calculate maximum sum
// of array after removing pairs whose
// concatenation is divisible by 3
void getMax(int arr[], int n)
{
 
    // Stores the sum of
    // digits of array element
    int maxRem0 = 0;
 
    int rem1 = 0;
    int rem2 = 0;
 
    for(int i = 0; i < n; i++)
    {
         
        // Find the sum of digits
        int digitSum = getSum(arr[i]);
 
        // If i is divisible by 3
        if (digitSum % 3 == 0)
            maxRem0 = max(maxRem0, arr[i]);
 
        // Otherwise, if i modulo 3 is 1
        else if (digitSum % 3 == 1)
            rem1 += arr[i];
 
        // Otherwise, if i modulo 3 is 2
        else
            rem2 += arr[i];
    }
 
    // Return the resultant
    // sum of array elements
    cout << (maxRem0 + max(rem1, rem2));
}
 
// Driver Code
int main()
{
    int arr[] = { 23, 12, 43, 3, 56 };
    int n = sizeof(arr) / sizeof(arr[0]);
     
    getMax(arr, n);
}
 
// This code is contributed by ukasp

// Java approach for the above approach
class GFG{
 
// Function to calculate sum
// of digits of an integer
static int getSum(int n)
{
    int ans = 0;
    char[] arr = (String.valueOf(n)).toCharArray();
     
    for(char ch : arr)
    {
        ans += Character.getNumericValue(ch);
    }
    return ans;
}
 
// Function to calculate maximum sum
// of array after removing pairs whose
// concatenation is divisible by 3
static void getMax(int[] arr)
{
     
    // Stores the sum of
    // digits of array element
    int maxRem0 = 0;
 
    int rem1 = 0;
    int rem2 = 0;
 
    for(int i:arr)
    {
         
        // Find the sum of digits
        int digitSum = getSum(i);
 
        // If i is divisible by 3
        if (digitSum % 3 == 0)
            maxRem0 = Math.max(maxRem0, i);
 
        // Otherwise, if i modulo 3 is 1
        else if (digitSum % 3 == 1)
            rem1 += i;
 
        // Otherwise, if i modulo 3 is 2
        else
            rem2 += i;
    }
     
    // Return the resultant
    // sum of array elements
    System.out.print(maxRem0 +
                     Math.max(rem1, rem2));
}
 
// Driver Code
public static void main(String[] args)
{
    int[] arr = { 23, 12, 43, 3, 56 };
    getMax(arr);
}
}
 
// This code is contributed by abhinavjain194

# Python3 program for the above approach
 
# Function to calculate sum
# of digits of an integer
def getSum(n):
  ans = 0
  for i in str(n):
    ans += int(i)
     
  return ans
 
# Function to calculate maximum sum
# of array after removing pairs whose
# concatenation is divisible by 3
def getMax(arr):
       
    # Stores the sum of
    # digits of array element
    maxRem0 = 0
     
    rem1 = 0
    rem2 = 0
 
    for i in arr:
       
        # Find the sum of digits
        digitSum = getSum(i)
         
        # If i is divisible by 3
        if digitSum % 3 == 0:
            maxRem0 = max(maxRem0, i)
             
        # Otherwise, if i modulo 3 is 1
        elif digitSum % 3 == 1:
            rem1 += i
                         
        # Otherwise, if i modulo 3 is 2
        else:
            rem2 += i
             
    # Return the resultant
    # sum of array elements
    print( maxRem0 + max(rem1, rem2))
 
# Driver Code
 
# Given array
arr = [ 23, 12, 43, 3, 56 ]
getMax(arr)

// C# program for the above approach
using System;
 
class GFG{
     
  
// Function to calculate sum
// of digits of an integer
static int getSum(int n)
{
    int ans = 0;
    string str = n.ToString();
    Char[] arr = str.ToCharArray();
      
    foreach(Char ch in arr)
    {
        ans += (int)Char.GetNumericValue(ch);
    }
    return ans;
}
  
// Function to calculate maximum sum
// of array after removing pairs whose
// concatenation is divisible by 3
static void getMax(int[] arr)
{
      
    // Stores the sum of
    // digits of array element
    int maxRem0 = 0;
  
    int rem1 = 0;
    int rem2 = 0;
  
    foreach(int i in arr)
    {
          
        // Find the sum of digits
        int digitSum = getSum(i);
  
        // If i is divisible by 3
        if (digitSum % 3 == 0)
            maxRem0 = Math.Max(maxRem0, i);
  
        // Otherwise, if i modulo 3 is 1
        else if (digitSum % 3 == 1)
            rem1 += i;
  
        // Otherwise, if i modulo 3 is 2
        else
            rem2 += i;
    }
      
    // Return the resultant
    // sum of array elements
    Console.WriteLine(maxRem0 +
                     Math.Max(rem1, rem2));
}
 
 
// Driver Code
static void Main()
{
    int[] arr = { 23, 12, 43, 3, 56 };
    getMax(arr);
}
}
 
// This code is contributed by souravghosh0416.

<script>
 
        // Javascript program for the
        // above approach
 
        // Function to calculate sum
        // of digits of an integer
        function getSum(n) {
            let ans = 0;
 
            let arr = n.toString();
            for (let i = 0; i < arr.length; i++)
            {
                ans += arr[i];
            }
            return ans;
        }
 
        // Function to calculate maximum sum
        // of array after removing pairs whose
        // concatenation is divisible by 3
        function getMax(arr, n) {
 
            // Stores the sum of
            // digits of array element
            let maxRem0 = 0;
 
            let rem1 = 0;
            let rem2 = 0;
 
            for (let i = 0; i < n; i++) {
 
                // Find the sum of digits
                let digitSum = getSum(arr[i]);
 
                // If i is divisible by 3
                if (digitSum % 3 == 0)
                    maxRem0 = Math.max(maxRem0, arr[i]);
 
                // Otherwise, if i modulo 3 is 1
                else if (digitSum % 3 == 1)
                    rem1 += arr[i];
 
                // Otherwise, if i modulo 3 is 2
                else
                    rem2 += arr[i];
            }
 
            // Return the resultant
            // sum of array elements
            document.write(maxRem0 + Math.max(rem1, rem2))
        }
 
        // Driver Code
        let arr = [23, 12, 43, 3, 56];
        let n = arr.length;
 
        getMax(arr, n);
 
        // This code is contributed by Hritik
         
    </script>

91

Complejidad temporal: O(N)
Espacio auxiliar: O(1)