Encuentre el par de suma máxima con la suma del mismo dígito

Dada una array arr que tiene N enteros, la tarea es encontrar un par con suma máxima y que tenga la misma suma de dígitos. Imprime la suma de ese par, si existe. De lo contrario, imprima -1 .

Ejemplos: 

Entrada:  arr[]={55, 23, 32, 46, 88}
Salida:  46 55 101
Explicación: El par {55, 46} dará la suma de 55 + 46 = 101 

Entrada: arr[]={18, 19, 23, 15}
Salida: -1

 

Enfoque: siga los pasos a continuación para resolver este problema:

  1. Cree un mapa, digamos mp para almacenar la suma de dígitos en un número como clave y el número máximo que tiene esa suma de dígitos como valor.
  2. Ahora cree una variable global y almacene la respuesta a este problema.
  3. Ahora comience a recorrer la array y en cada iteración:
    • Compruebe si la suma de su dígito ya está presente en el mapa. Si es así, cambia ans con el máximo de ans y la suma de los dos números.
    • Si la suma de los dígitos no está presente en el mapa. Cree una nueva clave para él y almacene su valor. De lo contrario, actualice el número en el mapa si es mayor que el número existente.
  4. Devuelve ans como la respuesta a este problema.

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

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find sum of digits
int digitSum(long n)
{
    long sum = 0;
    while (n) {
        sum += (n % 10);
        n /= 10;
    }
    return sum;
}
 
// Function to find maximum sum pair
// having the same sum of digits
void findMax(vector<int> arr, int n)
{
    // Map to store the sum of digits
    // in a number as the key and
    // the maximum number having
    // that sum of digits as the value
    unordered_map<int, int> mp;
    int ans = -1, pairi = 0, pairj = 0;
    for (int i = 0; i < n; i++) {
 
        // Store the current sum of digits
        // of the number in temp
        int temp = digitSum(arr[i]);
 
        // If temp is already present
        // in the map then update
        // ans if the sum is greater
        // than the existing value
        if (mp[temp] != 0) {
            if (arr[i] + mp[temp] > ans) {
                pairi = arr[i];
                pairj = mp[temp];
                ans = pairi + pairj;
            }
        }
 
        // Change the value in the map
        mp[temp] = max(arr[i], mp[temp]);
    }
 
    cout << pairi << " " << pairj
         << " " << ans << endl;
}
 
// Driver Code Starts.
int main()
{
    vector<int> arr = { 55, 23, 32, 46, 88 };
    int n = arr.size();
    findMax(arr, n);
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to find sum of digits
static int digitSum(long n)
{
    int sum = 0;
    while (n > 0)
    {
        sum += (n % 10);
        n /= 10;
    }
    return sum;
}
 
// Function to find maximum sum pair
// having the same sum of digits
static void findMax(int []arr, int n)
{
   
    // Map to store the sum of digits
    // in a number as the key and
    // the maximum number having
    // that sum of digits as the value
    HashMap<Integer,Integer> mp = new HashMap<Integer,Integer>();
    int ans = -1, pairi = 0, pairj = 0;
    for (int i = 0; i < n; i++) {
 
        // Store the current sum of digits
        // of the number in temp
        int temp = digitSum(arr[i]);
 
        // If temp is already present
        // in the map then update
        // ans if the sum is greater
        // than the existing value
        if (mp.containsKey(temp)) {
            if (arr[i] + mp.get(temp) > ans) {
                pairi = arr[i];
                pairj = mp.get(temp);
                ans = pairi + pairj;
            }
            mp.put(temp, Math.max(arr[i], mp.get(temp)));
        }
        else
        // Change the value in the map
        mp.put(temp, arr[i]);
         
    }
 
    System.out.print(pairi+ " " +  pairj
        + " " +  ans +"\n");
}
 
// Driver Code Starts.
public static void main(String[] args)
{
    int []arr = { 55, 23, 32, 46, 88 };
    int n = arr.length;
    findMax(arr, n);
}
}
 
// This code is contributed by shikhasingrajput

Python3

# Python Program to implement
# the above approach
 
# Function to find sum of digits
def digitSum(n):
    sum = 0
    while (n):
        sum += (n % 10)
        n = n // 10
    return sum
 
# Function to find maximum sum pair
# having the same sum of digits
def findMax(arr, n):
 
    # Map to store the sum of digits
    # in a number as the key and
    # the maximum number having
    # that sum of digits as the value
    mp = {}
    ans = -1
    pairi = 0
    pairj = 0
    for i in range(n):
 
        # Store the current sum of digits
        # of the number in temp
        temp = digitSum(arr[i])
 
        # If temp is already present
        # in the map then update
        # ans if the sum is greater
        # than the existing value
        if (temp not in mp):
            mp[temp] = 0
         
        if (mp[temp] != 0) :
            if (arr[i] + mp[temp] > ans):
                pairi = arr[i]
                pairj = mp.get(temp)
                ans = pairi + pairj
             
        # Change the value in the map
        mp[temp] = max(arr[i], mp[temp])
    print(f"{pairi} {pairj} {ans}")
 
# Driver Code Starts.
arr = [55, 23, 32, 46, 88]
n = len(arr)
findMax(arr, n)
 
# This code is contributed by Saurabh Jaiswal

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to find sum of digits
static int digitSum(long n)
{
    int sum = 0;
    while (n > 0)
    {
        sum += (int)(n % 10);
        n /= 10;
    }
    return sum;
}
 
// Function to find maximum sum pair
// having the same sum of digits
static void findMax(int []arr, int n)
{
   
    // Map to store the sum of digits
    // in a number as the key and
    // the maximum number having
    // that sum of digits as the value
    Dictionary<int,int> mp = new Dictionary<int, int>();
    int ans = -1, pairi = 0, pairj = 0;
    for (int i = 0; i < n; i++) {
 
        // Store the current sum of digits
        // of the number in temp
        int temp = digitSum(arr[i]);
 
        // If temp is already present
        // in the map then update
        // ans if the sum is greater
        // than the existing value
        if (mp.ContainsKey(temp)) {
            if (arr[i] + mp[temp] > ans) {
                pairi = arr[i];
                pairj = mp[temp];
                ans = pairi + pairj;
            }
            mp[temp] = Math.Max(arr[i], mp[temp]);
        }
        else
        // Change the value in the map
        mp[temp] = arr[i];
         
    }
 
    Console.WriteLine(pairi+ " " +  pairj + " " +  ans );
}
 
// Driver Code Starts.
public static void Main()
{
    int []arr = { 55, 23, 32, 46, 88 };
    int n = arr.Length;
    findMax(arr, n);
}
}
 
// This code is contributed by Saurabh Jaiswal

Javascript

<script>
 
       // JavaScript Program to implement
       // the above approach
 
       // Function to find sum of digits
       function digitSum(n) {
           let sum = 0;
           while (n) {
               sum += (n % 10);
               n = Math.floor(n / 10);
           }
           return sum;
       }
 
       // Function to find maximum sum pair
       // having the same sum of digits
       function findMax(arr, n)
       {
        
           // Map to store the sum of digits
           // in a number as the key and
           // the maximum number having
           // that sum of digits as the value
           let mp = new Map();
           let ans = -1, pairi = 0, pairj = 0;
           for (let i = 0; i < n; i++) {
 
               // Store the current sum of digits
               // of the number in temp
               let temp = digitSum(arr[i]);
 
               // If temp is already present
               // in the map then update
               // ans if the sum is greater
               // than the existing value
 
               if (!mp.has(temp)) {
                   mp.set(temp, 0);
               }
               if (mp.get(temp) != 0) {
                   if (arr[i] + mp.get(temp) > ans) {
                       pairi = arr[i];
                       pairj = mp.get(temp);
                       ans = pairi + pairj;
                   }
               }
 
               // Change the value in the map
               mp.set(temp, Math.max(arr[i], mp.get(temp)));
           }
 
           document.write(pairi + " " + pairj
               + " " + ans + '<br>');
       }
 
       // Driver Code Starts.
       let arr = [55, 23, 32, 46, 88];
       let n = arr.length;
       findMax(arr, n);
 
   // This code is contributed by Potta Lokesh
   </script>
Producción

46 55 101

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

Publicación traducida automáticamente

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