Diferencia entre máximo y mínimo de un conjunto de anagramas de una array

Dada una array arr[] que consta de N enteros, la tarea es encontrar los enteros cuyos dígitos son anagramas entre sí e imprimir la diferencia entre su máximo y mínimo. Si ninguno de los números forma anagramas, imprima -1 . 

Nota: como máximo, un conjunto de elementos de array puede ser anagramas entre sí. La array contiene al menos dos números y todos los números de la array dada tienen la misma longitud.

Ejemplos:

Entrada: arr[] = {121, 312, 234, 211, 112, 102}
Salida: 99
Explicación: En la array dada, el conjunto {121, 211, 112} son anagramas entre sí.
El valor más grande del conjunto es 211. 
El valor más pequeño del conjunto es 112.
Por lo tanto, diferencia = 211 – 112 = 99.

Entrada: arr[] = {345, 441, 604, 189, 113}
Salida: -1

Enfoque: La idea es usar Hashing para determinar los anagramas generando un valor hash único para cada número de anagrama. Siga los pasos a continuación para resolver el problema:

• Utilice números primos para fines de hashing y asigne los primeros 10 números primos a los dígitos 0-9 inicializando una array primo[10] con los primeros 10 números primos.

primo[10] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}  
primo[0] = 2 es decir, el número primo correspondiente al dígito 0 es «2»
primo[1] = 3 es decir, el número primo correspondiente al dígito 1 es «3»
primo[2] = 5 es decir, el número primo correspondiente al dígito 2 es «5» y así sucesivamente…

• Luego, encuentre el valor hash de cada elemento de la array arr[i] multiplicando el número primo correspondiente a cada dígito de arr[i] . De esta forma, el valor hash será diferente para los números que no sean anagramas.
• Encuentre el valor hash h para cada elemento de la array arr[i] usando la función hash(N) .
• Almacene los elementos de la array en el mapa con la clave como su valor hash h .
• Recorra el mapa para encontrar un vector con un tamaño mayor que 1 y encuentre sus elementos máximo y mínimo. Si dicho vector no está presente, imprima -1.

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Utility function to find the hash value
// for each element of the given array
int hashFunction(int N)
{
    // Initialize an array with
    // first 10 prime numbers
    int prime[10] = { 2, 3, 5, 7, 11,
                      13, 17, 19, 23, 29 };
 
    int value = 1, r;
 
    // Iterate over digits of N
    while (N != 0) {
        r = N % 10;
 
        // Update Hash Value
        value = value * prime[r];
 
        // Update N
        N = N / 10;
    }
    return value;
}
 
// Function to find the set of anagrams in the array
// and print the difference between the maximum and
// minimum of these numbers
void findDiff(int arr[], int n)
{
 
    // Map to store the hash value
    // and the array elements having that hash value
    map<int, vector<int> > m;
 
    int h, min, max;
    for (int i = 0; i < n; i++) {
 
        // Find the hash value for each arr[i]
        // by calling hash function
        h = hashFunction(arr[i]);
 
        m[h].push_back(arr[i]);
    }
 
    // Iterate over the map
    for (auto i = 0; i != m.size(); i++) {
 
        // If size of vector at m[i] greater than 1
        // then it must contain the anagrams
        if (m[i].size() > 1) {
 
            // Find the minimum and maximum
            // element of this anagrams vector
            min = *min_element(
                m[i].begin(), m[i].end());
            max = *max_element(
                m[i].begin(), m[i].end());
 
            // Display the difference
            cout << max - min;
            break;
        }
 
        // If the end of Map is reached,
        // then no anagrams are present
        else if (i == m.size() - 1)
            cout << -1;
    }
}
 
// Driver Code
int main()
{
    // Given array
    int arr[] = { 121, 312, 234,
                  211, 112, 102 };
 
    // Size of the array
    int N = sizeof(arr)
            / sizeof(arr[0]);
 
    findDiff(arr, N);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Utility function to find the hash value
// for each element of the given array
static int hashFunction(int N)
{
     
    // Initialize an array with
    // first 10 prime numbers
    int[] prime = { 2, 3, 5, 7, 11, 13,
                    17, 19, 23, 29 };
     
    int value = 1, r;
     
    // Iterate over digits of N
    while (N != 0)
    {
        r = N % 10;
         
        // Update Hash Value
        value = value * prime[r];
         
        // Update N
        N = N / 10;
    }
    return value;
}
 
// Function to find the set of anagrams in the array
// and print the difference between the maximum and
// minimum of these numbers
static void findDiff(int[] arr, int n)
{
     
    // Map to store the hash value
    // and the array elements having that hash value
    HashMap<Integer, Vector<Integer>> m = new HashMap<>();
     
    int h, min, max;
    for(int i = 0; i < n; i++)
    {
         
        // Find the hash value for each arr[i]
        // by calling hash function
        h = hashFunction(arr[i]);
         
        if (!m.containsKey(h))
        {
            m.put(h, new Vector<Integer>());
        }
         
        m.get(h).add(arr[i]);
    }
     
    for(Map.Entry<Integer, Vector<Integer>> i : m.entrySet())
    {
         
        // If size of vector at m[i] greater than 1
        // then it must contain the anagrams
        if (i.getValue().size() > 1)
        {
         
            // Find the minimum and maximum
            // element of this anagrams vector
            min = Integer.MAX_VALUE;
            max = -(Integer.MAX_VALUE);
             
            for (int j = 0; j < i.getValue().size(); j++)
            {
                if (m.get(i.getKey()).get(j) < min)
                {
                    min = m.get(i.getKey()).get(j);
                }
                 
                if (m.get(i.getKey()).get(j) > max)
                {
                    max = m.get(i.getKey()).get(j);
                }
            }
             
            // Display the difference
            System.out.print(max - min);
            break;
        }
         
        // If the end of Map is reached,
        // then no anagrams are present
        else if (m.get(i.getKey()) == m.values().toArray()[m.size() - 1])
            System.out.print(-1);
    }
}
 
// Driver code
public static void main(String[] args)
{
    // Given array
    int[] arr = { 121, 312, 234,
                 211, 112, 102 };
  
    // Size of the array
    int N = arr.length;
  
    findDiff(arr, N);
}
}
 
// This code is contributed by divyeshrabadiya07

# Python3 program for the above approach
import math
from collections import defaultdict
 
# Utility function to find the hash value
# for each element of the given array
def hashFunction(N) :
     
    # Initialize an array with
    # first 10 prime numbers
    prime = [ 2, 3, 5, 7, 11,
                      13, 17, 19, 23, 29 ]
    value = 1
 
    # Iterate over digits of N
    while (N != 0) :
        r = N % 10
 
        # Update Hash Value
        value = value * prime[r]
 
        # Update N
        N = N // 10
    return value
 
# Function to find the set of anagrams in the array
# and print the difference between the maximum and
# minimum of these numbers
def findDiff(arr, n):
 
    # Map to store the hash value
    # and the array elements having that hash value
    m = defaultdict(lambda : [])
    for i in range(n):
 
        # Find the hash value for each arr[i]
        # by calling hash function
        h = hashFunction(arr[i])
        m[h].append(arr[i])
     
    # Iterate over the map
    i = 0
    while(i != len(m)) :
 
        # If size of vector at m[i] greater than 1
        # then it must contain the anagrams
        if (len(m[i]) > 1) :
 
            # Find the minimum and maximum
            # element of this anagrams vector
            minn = min(m[i])
            maxx = max(m[i])
 
            # Display the difference
            print(maxx - minn)
            break
         
        # If the end of Map is reached,
        # then no anagrams are present
        elif (i == (len(m) - 1)) :
            print(-1)   
        i += 1
     
# Driver Code
 
# Given array
arr = [ 121, 312, 234,
                211, 112, 102 ]
 
# Size of the array
N = len(arr)
findDiff(arr, N)
 
# This code is contributed by sanjoy_62.

// C# program for the above approach
using System;
using System.Collections.Generic;
using System.Linq;
class GFG {
 
  // Utility function to find the hash value
  // for each element of the given array
  static int hashFunction(int N)
  {
    // Initialize an array with
    // first 10 prime numbers
    int[] prime = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 };
 
    int value = 1, r;
 
    // Iterate over digits of N
    while (N != 0) {
      r = N % 10;
 
      // Update Hash Value
      value = value * prime[r];
 
      // Update N
      N = N / 10;
    }
    return value;
  }
 
  // Function to find the set of anagrams in the array
  // and print the difference between the maximum and
  // minimum of these numbers
  static void findDiff(int[] arr, int n)
  {
 
    // Map to store the hash value
    // and the array elements having that hash value
    Dictionary<int, List<int>> m = new Dictionary<int, List<int>>();
 
    int h, min, max;
    for (int i = 0; i < n; i++) {
 
      // Find the hash value for each arr[i]
      // by calling hash function
      h = hashFunction(arr[i]);
 
      if(!m.ContainsKey(h))
      {
        m[h] = new List<int>();
      }
 
      m[h].Add(arr[i]);
    }
 
    // Iterate over the map
    foreach(KeyValuePair<int, List<int>> i in m)
    {
      // If size of vector at m[i] greater than 1
      // then it must contain the anagrams
      if (i.Value.Count > 1) {
 
        // Find the minimum and maximum
        // element of this anagrams vector
        min = Int32.MaxValue;
        max = Int32.MinValue;
        for(int j = 0; j < i.Value.Count; j++)
        {
          if(m[i.Key][j] < min)
          {
            min = m[i.Key][j];
          }
 
          if(m[i.Key][j] > max)
          {
            max = m[i.Key][j];
          }
        }
 
        // Display the difference
        Console.Write(max - min);
        break;
      }
 
      // If the end of Map is reached,
      // then no anagrams are present
      else if (m[i.Key].Equals( m.Last().Value ))
        Console.Write(-1);
    }
  }
 
  // Driver code
  static void Main()
  {
    // Given array
    int[] arr = { 121, 312, 234,
                 211, 112, 102 };
 
    // Size of the array
    int N = arr.Length;
 
    findDiff(arr, N);
  }
}
 
// This code is contributed by divyesh072019.

<script>
    // Javascript program for the above approach
     
    // Utility function to find the hash value
    // for each element of the given array
    function hashFunction(N)
    {
 
        // Initialize an array with
        // first 10 prime numbers
        let prime = [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ];
 
        let value = 1, r;
 
        // Iterate over digits of N
        while (N != 0)
        {
            r = N % 10;
 
            // Update Hash Value
            value = value * prime[r];
 
            // Update N
            N = parseInt(N / 10, 10);
        }
        return value;
    }
     
    // Function to find the set of anagrams in the array
    // and print the difference between the maximum and
    // minimum of these numbers
    function findDiff(arr, n)
    {
 
      // Map to store the hash value
      // and the array elements having that hash value
      let m = new Map();
 
      let h, min, max;
      for (let i = 0; i < n; i++) {
 
        // Find the hash value for each arr[i]
        // by calling hash function
        h = hashFunction(arr[i]);
 
        if(!m.has(h))
        {
          m.set(h, []);
        }
 
        (m.get(h)).push(arr[i]);
      }
 
      // Iterate over the map
      m.forEach((values,keys)=>{
        // If size of vector at m[i] greater than 1
        // then it must contain the anagrams
        if (values.length > 1) {
 
          // Find the minimum and maximum
          // element of this anagrams vector
          min = Number.MAX_VALUE;
          max = Number.MIN_VALUE;
          for(let j = 0; j < values.length; j++)
          {
            if((m.get(keys))[j] < min)
            {
              min = m.get(keys)[j];
            }
 
            if(m.get(keys)[j] > max)
            {
              max = m.get(keys)[j];
            }
          }
 
          // Display the difference
          document.write(max - min);
        }
      })
    }
     
    // Given array
    let arr = [ 121, 312, 234, 211, 112, 102 ];
  
    // Size of the array
    let N = arr.length;
  
    findDiff(arr, N);
 
// This code is contributed by suresh07.
</script>

99

Complejidad de tiempo : O(N*logN)
Espacio auxiliar: O(N)