Conteo de dígitos en N y M que son iguales pero están presentes en diferentes índices

Dados dos números N y M , la tarea es encontrar el conteo de dígitos en N y M que son iguales pero están presentes en diferentes índices.

Ejemplos:

Entrada: N = 123, M = 321
Salida: 2
Explicación: Los dígitos 1 y 3 cumplen la condición

Entrada: N = 123, M = 111
Salida: 0

 

Enfoque: el problema se puede resolver utilizando hash y enfoque de dos puntos.

  • Convierta N y M en strings para facilitar el recorrido
  • Ahora cree 2 hash de tamaño 10 para almacenar la frecuencia de los dígitos en N y M respectivamente
  • Ahora recorre un bucle de 0 a 9 y:
    • Agregue min de hashN[i] y hashM[i] a un conteo variable
  • Ahora recorra los números usando dos punteros para encontrar el conteo de dígitos que son iguales y ocurren en los mismos índices tanto en N como en M. Almacene el conteo en la variable same_dig_cnt
  • Ahora devuelve el conteo final como conteo – same_dig_cnt

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

C++

// C++ implementation of the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
int countDigits(int N, int M)
{
 
    // Convert N and M to string
    // for ease of traversal
    string a = to_string(N), b = to_string(M);
 
    // Create 2 hash of size 10
    // to store frequency of digits
    // in N and M respectively
    vector<int> hashN(10, 0);
    for (char c : a)
        hashN++;
    vector<int> hashM(10, 0);
    for (char c : b)
        hashM++;
 
    int count = 0, same_dig_cnt = 0;
 
    // Count of common digits
    // irrespective of their positions
    for (int i = 0; i < 10; i++)
        count += min(hashN[i], hashM[i]);
 
    // Find the count of digits
    // that are same and occur on same indices
    // in both N and M.
    // Store the count in variable same_dig_cnt
    for (int i = 0; i < a.length() && b.length(); i++)
        if (a[i] == b[i])
            same_dig_cnt++;
 
    // Remove the count of digits that are
    // not at same indices in both numbers
    count -= same_dig_cnt;
 
    return count;
}
 
// Driver code
int main()
{
 
    int N = 123, M = 321;
 
    cout << countDigits(N, M);
    return 0;
}

Java

// Java implementation of the above approach
class GFG {
 
  static int countDigits(int N, int M) {
 
    // Convert N and M to string
    // for ease of traversal
    String a = Integer.toString(N), b = Integer.toString(M);
 
    // Create 2 hash of size 10
    // to store frequency of digits
    // in N and M respectively
    int[] hashN = new int[10];
 
    for (int i = 0; i < 10; i++) {
      hashN[i] = 0;
    }
 
    for (char c : a.toCharArray()) {
      hashN++;
    }
 
    int[] hashM = new int[10];
 
    for (int i = 0; i < 10; i++) {
      hashM[i] = 0;
    }
 
    for (char c : a.toCharArray()) {
      hashM++;
    }
 
    int count = 0, same_dig_cnt = 0;
 
    // Count of common digits
    // irrespective of their positions
    for (int i = 0; i < 10; i++)
      count += Math.min(hashN[i], hashM[i]);
 
    // Find the count of digits
    // that are same and occur on same indices
    // in both N and M.
    // Store the count in variable same_dig_cnt
    for (int i = 0; i < a.length() && i < b.length(); i++)
      if (a.charAt(i) == b.charAt(i))
        same_dig_cnt++;
 
    // Remove the count of digits that are
    // not at same indices in both numbers
    count -= same_dig_cnt;
 
    return count;
  }
 
  // Driver code
  public static void main(String args[])
  {
    int N = 123, M = 321;
    System.out.println(countDigits(N, M));
  }
}
 
// This code is contributed by gfgking

Python3

# Python code for the above approach
def countDigits(N, M):
 
    # Convert N and M to string
    # for ease of traversal
    a = str(N)
    b = str(M)
 
    # Create 2 hash of size 10
    # to store frequency of digits
    # in N and M respectively
    hashN = [0] * 10
    for c in range(len(a)):
        hashN[ord(a) - ord('0')] += 1
 
    hashM = [0] * 10
    for c in range(len(b)):
        hashM[ord(b) - ord('0')] += 1
 
    count = 0
    same_dig_cnt = 0;
 
    # Count of common digits
    # irrespective of their positions
    for i in range(10):
        count += min(hashN[i], hashM[i]);
 
    # Find the count of digits
    # that are same and occur on same indices
    # in both N and M.
    # Store the count in variable same_dig_cnt
    i = 0
    while(i < len(a) and len(b)):
        if (a[i] == b[i]):
            same_dig_cnt += 1
        i += 1
 
    # Remove the count of digits that are
    # not at same indices in both numbers
    count -= same_dig_cnt;
 
    return count;
 
# Driver code
N = 123
M = 321;
 
print(countDigits(N, M));
 
# This code is contributed by Saurabh Jaiswal

C#

// C# implementation of the above approach
using System;
using System.Collections;
class GFG
{
 
  static int countDigits(int N, int M)
  {
 
    // Convert N and M to string
    // for ease of traversal
    string a = N.ToString(), b = M.ToString();
 
    // Create 2 hash of size 10
    // to store frequency of digits
    // in N and M respectively
    int []hashN = new int[10];
 
    for(int i = 0; i < 10; i++) {
      hashN[i] = 0;
    }
 
    foreach (char c in a) {
      hashN++;
    }
 
    int []hashM = new int[10];
 
    for(int i = 0; i < 10; i++) {
      hashM[i] = 0;
    }
 
    foreach (char c in a) {
      hashM++;
    }
 
    int count = 0, same_dig_cnt = 0;
 
    // Count of common digits
    // irrespective of their positions
    for (int i = 0; i < 10; i++)
      count += Math.Min(hashN[i], hashM[i]);
 
    // Find the count of digits
    // that are same and occur on same indices
    // in both N and M.
    // Store the count in variable same_dig_cnt
    for (int i = 0; i < a.Length && i < b.Length; i++)
      if (a[i] == b[i])
        same_dig_cnt++;
 
    // Remove the count of digits that are
    // not at same indices in both numbers
    count -= same_dig_cnt;
 
    return count;
  }
 
  // Driver code
  public static void Main()
  {
 
    int N = 123, M = 321;
 
    Console.Write(countDigits(N, M));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

Javascript

<script>
       // JavaScript code for the above approach
       function countDigits(N, M)
       {
 
           // Convert N and M to string
           // for ease of traversal
           let a = (N).toString(), b = (M).toString();
 
           // Create 2 hash of size 10
           // to store frequency of digits
           // in N and M respectively
           let hashN = new Array(10).fill(0);
           for (let c = 0; c < a.length; c++)
               hashN[a.charCodeAt(0) - '0'.charCodeAt(0)]++;
           let hashM = new Array(10).fill(0);
           for (c = 0; c < b.length; c++)
               hashM[b.charCodeAt(0) - '0'.charCodeAt(0)]++;
 
           let count = 0, same_dig_cnt = 0;
 
           // Count of common digits
           // irrespective of their positions
           for (let i = 0; i < 10; i++)
               count += Math.min(hashN[i], hashM[i]);
 
           // Find the count of digits
           // that are same and occur on same indices
           // in both N and M.
           // Store the count in variable same_dig_cnt
           for (let i = 0; i < a.length && b.length; i++)
               if (a[i] == b[i])
                   same_dig_cnt++;
 
           // Remove the count of digits that are
           // not at same indices in both numbers
           count -= same_dig_cnt;
 
           return count;
       }
 
       // Driver code
       let N = 123, M = 321;
 
       document.write(countDigits(N, M));
 
      // This code is contributed by Potta Lokesh
   </script>
Producción

2

Complejidad de tiempo: O(D), donde D es el conteo máximo de dígitos en N o M
Espacio auxiliar: O(D), donde D es el conteo máximo de dígitos en N o M

Publicación traducida automáticamente

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