Dada una array arr[] de N enteros distintos. La tarea es encontrar la suma de dos números enteros de array a[i] + a[j] que ocurre el número máximo de veces. En el caso de respuestas múltiples, imprímalas todas.
Ejemplos:
Entrada: arr[] = {1, 8, 3, 11, 4, 9, 2, 7}
Salida:
10
12
11
La suma de 10, 12 y 11 ocurre 3 veces
7 + 4 = 11, 8 + 3 = 11, 9 + 2 = 11
1 + 9 = 10, 8 + 2 = 10, 7 + 3 = 10
1 + 11 = 12, 8 + 4 = 12, 9 + 3 = 12
Entrada: arr[] = {3, 1, 7, 11, 9, 2, 12}
Salida:
12
14
10
13
Enfoque: Se pueden seguir los siguientes pasos para resolver el problema:
- Iterar sobre cada par de elementos.
- Use una tabla hash para contar el número de veces que ocurre cada par de sumas.
- Al final, itera sobre la tabla hash y encuentra el par de suma que ocurre la mayor cantidad de veces.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the sum pairs
// that occur the most
void findSumPairs(int a[], int n)
{
// Hash-table
unordered_map<int, int> mpp;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
// Keep a count of sum pairs
mpp[a[i] + a[j]]++;
}
}
// Variables to store
// maximum occurrence
int occur = 0;
// Iterate in the hash table
for (auto it : mpp) {
if (it.second > occur) {
occur = it.second;
}
}
// Print all sum pair which occur
// maximum number of times
for (auto it : mpp) {
if (it.second == occur)
cout << it.first << endl;
}
}
// Driver code
int main()
{
int a[] = { 1, 8, 3, 11, 4, 9, 2, 7 };
int n = sizeof(a) / sizeof(a[0]);
findSumPairs(a, n);
return 0;
}
Java
// Java implementation of above approach
import java.util.*;
class GFG
{
// Function to find the sum pairs
// that occur the most
static void findSumPairs(int a[], int n)
{
// Hash-table
Map<Integer,Integer> mpp = new HashMap<>();
for (int i = 0; i < n - 1; i++)
{
for (int j = i + 1; j < n; j++)
{
// Keep a count of sum pairs
mpp.put(a[i] + a[j],mpp.get(a[i] + a[j])==null?1:mpp.get(a[i] + a[j])+1);
}
}
// Variables to store
// maximum occurrence
int occur = 0;
// Iterate in the hash table
for (Map.Entry<Integer,Integer> entry : mpp.entrySet())
{
if (entry.getValue() > occur)
{
occur = entry.getValue();
}
}
// Print all sum pair which occur
// maximum number of times
for (Map.Entry<Integer,Integer> entry : mpp.entrySet())
{
if (entry.getValue() == occur)
System.out.println(entry.getKey());
}
}
// Driver code
public static void main(String args[])
{
int a[] = { 1, 8, 3, 11, 4, 9, 2, 7 };
int n = a.length;
findSumPairs(a, n);
}
}
/* This code is contributed by PrinciRaj1992 */
Python3
# Python 3 implementation of the approach
# Function to find the sum pairs
# that occur the most
def findSumPairs(a, n):
# Hash-table
mpp = {i:0 for i in range(21)}
for i in range(n - 1):
for j in range(i + 1, n, 1):
# Keep a count of sum pairs
mpp[a[i] + a[j]] += 1
# Variables to store
# maximum occurrence
occur = 0
# Iterate in the hash table
for key, value in mpp.items():
if (value > occur):
occur = value
# Print all sum pair which occur
# maximum number of times
for key, value in mpp.items():
if (value == occur):
print(key)
# Driver code
if __name__ == '__main__':
a = [1, 8, 3, 11, 4, 9, 2, 7]
n = len(a)
findSumPairs(a, n)
# This code is contributed by
# Surendra_Gangwar
C#
// C# implementation of above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to find the sum pairs
// that occur the most
static void findSumPairs(int []a, int n)
{
// Hash-table
Dictionary<int,int> mpp = new Dictionary<int,int>();
for (int i = 0; i < n - 1; i++)
{
for (int j = i + 1; j < n; j++)
{
// Keep a count of sum pairs
if(mpp.ContainsKey(a[i] + a[j]))
{
var val = mpp[a[i] + a[j]];
mpp.Remove(a[i] + a[j]);
mpp.Add(a[i] + a[j], val + 1);
}
else
{
mpp.Add(a[i] + a[j], 1);
}
}
}
// Variables to store
// maximum occurrence
int occur = 0;
// Iterate in the hash table
foreach(KeyValuePair<int, int> entry in mpp)
{
if (entry.Value > occur)
{
occur = entry.Value;
}
}
// Print all sum pair which occur
// maximum number of times
foreach(KeyValuePair<int, int> entry in mpp)
{
if (entry.Value == occur)
Console.WriteLine(entry.Key);
}
}
// Driver code
public static void Main(String []args)
{
int []a = { 1, 8, 3, 11, 4, 9, 2, 7 };
int n = a.Length;
findSumPairs(a, n);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// javascript implementation of the approach
// Function to find the sum pairs
// that occur the most
function findSumPairs( a, n){
// Hash-table
let mpp = new Map();
for (let i = 0; i < n - 1; i++) {
for (let j = i + 1; j < n; j++) {
if(mpp[a[i]+a[j]])
mpp[a[i]+a[j]]++;
else
mpp[a[i]+a[j]] = 1;
}
}
// Variables to store
// maximum occurrence
let occur = 0;
// Iterate in the hash table
for (var it in mpp) {
if (mpp[it] > occur) {
occur = mpp[it];
}
}
// Print all sum pair which occur
// maximum number of times
for (var it in mpp) {
if (mpp[it] == occur)
document.write( it ,'<br>');
}
}
// Driver code
let a = [ 1, 8, 3, 11, 4, 9, 2, 7 ];
let len = a.length;
findSumPairs(a, len);
</script>
Producción:
10 12 11
Complejidad de tiempo: O (N * N), ya que estamos usando bucles anidados para atravesar N * N veces. Donde N es el número de elementos de la array.
Espacio auxiliar: O(N*N), ya que estamos usando espacio extra para el mapa. Donde N es el número de elementos de la array.