Cuente pares en una array que tenga una suma de elementos con su respectiva suma de dígitos igual

Posted on by Rudeus Greyrat

Dada una array arr[] que consiste en N enteros positivos, la tarea es contar el número de pares en la array , digamos (a, b) tal que la suma de a con su suma de dígitos sea igual a la suma de b con su suma de digitos

Ejemplos:

Entrada: arr[] = {1, 1, 2, 2}
Salida: 2
Explicación:
Los siguientes son los pares que satisfacen los criterios dados:

  1. (1, 1): La diferencia entre 1+ sumOfDigits(1) y 1+sumOfDigits(1) es 0, por lo que son iguales.
  2. (2, 2): La diferencia entre 2+sumOfDigits(2) y 2+sumOfDigits(2) es 0, por lo que son iguales.

Por lo tanto, el número total de pares es 2.

Entrada : arr[] = {105, 96, 20, 2, 87, 96}
Salida : 3
Los siguientes son los pares que satisfacen los criterios dados:

  1. (105, 96) : La diferencia entre 105+ sumOfDigits(105) y 96+sumOfDigits(96) es 0, por lo que son iguales.
  2. (105, 96) : La diferencia entre 105+ sumOfDigits(105) y 96+sumOfDigits(96) es 0, por lo que son iguales.
  3. (96, 96) : La diferencia entre 96+ sumOfDigits(96) y 96+sumOfDigits(96) es 0, por lo que son iguales.

Entrada: arr[] = {1, 2, 3, 4}
Salida: 0

Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todos los pares posibles de la array dada y contar los pares que satisfacen los criterios dados. Después de verificar todos los pares, imprima el recuento total de pares obtenidos.

Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)

Enfoque eficiente: el enfoque anterior también se puede optimizar almacenando la suma de elementos con su suma de dígitos en un HashMap y luego contar el número total de pares formados en consecuencia. Siga los pasos que se indican a continuación para resolver el problema:

  • Inicialice un mapa_desordenado , M que almacene la frecuencia de la suma de elementos con su suma de dígitos para cada elemento del arreglo.
  • Recorre la array dada e incrementa la frecuencia de (arr[i] + sumOfDigits(arr[i])) en el mapa M .
  • Inicialice una variable, digamos contar como 0 que almacena el recuento total de pares resultantes.
  • Recorra el mapa dado M y si la frecuencia de cualquier elemento , digamos F es mayor o igual a 2 , entonces incremente el valor de cuenta por (F*(F – 1))/2 .
  • Después de completar los pasos anteriores, imprima el valor de conteo como el conteo resultante de pares.

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 the sum of digits
// of the number N
int sumOfDigits(int N)
{
    // Stores the sum of digits
    int sum = 0;
 
    // If the number N is greater than 0
    while (N) {
        sum += (N % 10);
        N = N / 10;
    }
 
    // Return the sum
    return sum;
}
 
// Function to find the count of pairs
// such that arr[i] + sumOfDigits(arr[i])
// is equal to (arr[j] + sumOfDigits(arr[j])
int CountPair(int arr[], int n)
{
    // Stores the frequency of value
    // of arr[i] + sumOfDigits(arr[i])
    unordered_map<int, int> mp;
 
    // Traverse the given array
    for (int i = 0; i < n; i++) {
 
        // Find the value
        int val = arr[i] + sumOfDigits(arr[i]);
 
        // Increment the frequency
        mp[val]++;
    }
 
    // Stores the total count of pairs
    int count = 0;
 
    // Traverse the map mp
    for (auto x : mp) {
 
        int val = x.first;
        int times = x.second;
 
        // Update the count of pairs
        count += ((times * (times - 1)) / 2);
    }
 
    // Return the total count of pairs
    return count;
}
 
// Driver Code
int main()
{
    int arr[] = { 105, 96, 20, 2, 87, 96 };
    int N = sizeof(arr) / sizeof(arr[0]);
    cout << CountPair(arr, N);
 
    return 0;
}

Java

/*package whatever //do not write package name here */
import java.io.*;
import java.util.*;
class GFG
{
   
    // Function to find the sum of digits
    // of the number N
    static int sumOfDigits(int N)
    {
        // Stores the sum of digits
        int sum = 0;
 
        // If the number N is greater than 0
        while (N > 0) {
            sum += (N % 10);
            N = N / 10;
        }
 
        // Return the sum
        return sum;
    }
 
    // Function to find the count of pairs
    // such that arr[i] + sumOfDigits(arr[i])
    // is equal to (arr[j] + sumOfDigits(arr[j])
    static int CountPair(int arr[], int n)
    {
        // Stores the frequency of value
        // of arr[i] + sumOfDigits(arr[i])
        HashMap<Integer, Integer> mp
            = new HashMap<Integer, Integer>();
 
        // Traverse the given array
        for (int i = 0; i < n; i++) {
 
            // Find the value
            int val = arr[i] + sumOfDigits(arr[i]);
 
            // Increment the frequency
            if (mp.containsKey(val)) {
                mp.put(val, mp.get(val) + 1);
            }
            else {
                mp.put(val, 1);
            }
        }
 
        // Stores the total count of pairs
        int count = 0;
 
        // Traverse the map mp
        for (Map.Entry<Integer, Integer> x :
             mp.entrySet()) {
 
            int val = x.getKey();
            int times = x.getValue();
 
            // Update the count of pairs
            count += ((times * (times - 1)) / 2);
        }
 
        // Return the total count of pairs
        return count;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int arr[] = { 105, 96, 20, 2, 87, 96 };
        int N = 6;
        System.out.println(CountPair(arr, N));
    }
}
 
// This code is contributed by maddler.

Python3

# Python 3 program for the above approach
 
# Function to find the sum of digits
# of the number N
def sumOfDigits(N):
    # Stores the sum of digits
    sum = 0
 
    # If the number N is greater than 0
    while (N):
        sum += (N % 10)
        N = N // 10
 
    # Return the sum
    return sum
 
# Function to find the count of pairs
# such that arr[i] + sumOfDigits(arr[i])
# is equal to (arr[j] + sumOfDigits(arr[j])
def CountPair(arr, n):
    # Stores the frequency of value
    # of arr[i] + sumOfDigits(arr[i])
    mp = {}
 
    # Traverse the given array
    for i in range(n):
        # Find the value
        val = arr[i] + sumOfDigits(arr[i])
 
        # Increment the frequency
        if val in mp:
            mp[val] += 1
        else:
            mp[val] = 1
 
    # Stores the total count of pairs
    count = 0
 
    # Traverse the map mp
    for key,value in mp.items():
        val = key
        times = value
 
        # Update the count of pairs
        count += ((times * (times - 1)) // 2)
 
    # Return the total count of pairs
    return count
 
# Driver Code
if __name__ == '__main__':
    arr = [105, 96, 20, 2, 87, 96]
    N = len(arr)
    print(CountPair(arr, N))
     
    # This code is contributed by SURENDRA_GANGWAR.

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
  // Function to find the sum of digits
// of the number N
static int sumOfDigits(int N)
{
   
    // Stores the sum of digits
    int sum = 0;
 
    // If the number N is greater than 0
    while (N>0) {
        sum += (N % 10);
        N = N / 10;
    }
 
    // Return the sum
    return sum;
}
 
// Function to find the count of pairs
// such that arr[i] + sumOfDigits(arr[i])
// is equal to (arr[j] + sumOfDigits(arr[j])
static int CountPair(int []arr, int n)
{
    // Stores the frequency of value
    // of arr[i] + sumOfDigits(arr[i])
    Dictionary<int, int> mp = new Dictionary<int,int>();
 
    // Traverse the given array
    for (int i = 0; i < n; i++) {
 
        // Find the value
        int val = arr[i] + sumOfDigits(arr[i]);
 
        // Increment the frequency
        if(mp.ContainsKey(val))
         mp[val]++;
        else
         mp.Add(val,1);
    }
 
    // Stores the total count of pairs
    int count = 0;
 
    // Traverse the map mp
    foreach(KeyValuePair<int, int> entry in mp) {
 
        int val = entry.Key;
        int times = entry.Value;
 
        // Update the count of pairs
        count += ((times * (times - 1)) / 2);
    }
 
    // Return the total count of pairs
    return count;
}
 
// Driver Code
public static void Main()
{
    int []arr = { 105, 96, 20, 2, 87, 96 };
    int N = arr.Length;
    Console.Write(CountPair(arr, N));
}
}
 
// This code is contributed by ipg2016107.

Javascript

<script>
        // JavaScript Program to implement
        // the above approach
        // Function to find the sum of digits
        // of the number N
        function sumOfDigits(N) {
            // Stores the sum of digits
            let sum = 0;
 
            // If the number N is greater than 0
            while (N != 0) {
                sum = sum + (N % 10);
                N = Math.floor(N / 10);
            }
 
            // Return the sum
            return sum;
        }
 
        // Function to find the count of pairs
        // such that arr[i] + sumOfDigits(arr[i])
        // is equal to (arr[j] + sumOfDigits(arr[j])
        function CountPair(arr, n) {
            // Stores the frequency of value
            // of arr[i] + sumOfDigits(arr[i])
            let mp = new Map();
 
            // Traverse the given array
            for (let i = 0; i < n; i++) {
 
                // Find the value
 
 
                let val = arr[i] + sumOfDigits(arr[i]);
                // Increment the frequency
                if (mp.has(val)) {
                    mp.set(val, mp.get(val) + 1);
                }
                else {
                    mp.set(val, 1);
                }
            }
 
            // Stores the total count of pairs
            let count = 0;
 
            // Traverse the map mp
            for (let [key, value] of mp) {
 
                // Update the count of pairs
 
 
                count = count + (value * (value - 1)) / 2;
            }
 
            // Return the total count of pairs
            return count;
        }
 
        // Driver Code
 
        let arr = [105, 96, 20, 2, 87, 96];
        let N = arr.length;
        document.write(CountPair(arr, N))
 
 
// This code is contributed by Potta Lokesh
    </script>
Producción

3

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

Publicación traducida automáticamente

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