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 = 101Entrada: arr[]={18, 19, 23, 15}
Salida: -1
Enfoque: siga los pasos a continuación para resolver este problema:
- 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.
- Ahora cree una variable global y almacene la respuesta a este problema.
- 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.
- 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