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ónEntrada: 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