Dadas dos strings numéricas N y M , la tarea es codificar las strings dadas en la forma » xAyB «, donde:
- x es el conteo de dígitos que son iguales en N y M y están presentes en los mismos índices
- y es el conteo de dígitos que son iguales en N y M pero están presentes en diferentes índices
Ejemplos:
Entrada: N = 123, M = 321
Salida: “1A2B”
Explicación:
El dígito 2 cumple la condición para x como conteo de dígitos que son iguales en N y M y están presentes en los mismos índices Los
dígitos 1 y 3 satisfacen la condición para y como conteo de dígitos que son iguales en N y M pero están presentes en diferentes índicesEntrada: N = 123, M = 111
Salida: “0A1B”
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
- Por lo tanto x = mismo_dig_cnt, y = cuenta.
- Ahora devuelva la string final como «xAyB»
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;
// Function to encode strings as "xAyB"
string encodeStrings(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;
// Therefore x = same_dig_cnt, y = count.
// Now return the final string as "xAyB"
string ans = "" + to_string(same_dig_cnt) + "A"
+ to_string(count) + "B";
return ans;
}
// Driver code
int main()
{
int N = 1807, M = 7810;
cout << "\"" << encodeStrings(N, M) << "\"";
return 0;
}
Java
// java implementation of the above approach
class GFG {
// Function to encode Strings as "xAyB"
static String encodeStrings(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 : b.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;
// Therefore x = same_dig_cnt, y = count.
// Now return the final String as "xAyB"
String ans = "" + Integer.toString(same_dig_cnt) + "A" + Integer.toString(count) + "B";
return ans;
}
// Driver code
public static void main(String args[])
{
int N = 1807, M = 7810;
System.out.println("\"" + encodeStrings(N, M) + "\"");
}
}
// This code is contributed by Saurabh jaiswal
Python3
# Python code for the above approach
def encodeStrings(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
# Therefore x = same_dig_cnt, y = count.
# Now return the final string as "xAyB"
ans = str(same_dig_cnt) + "A" + str(count) + "B"
return ans
# Driver code
N = 1807
M = 7810
print(f"\"{encodeStrings(N, M)}\"")
# This code is contributed by Saurabh jaiswal
C#
// C# implementation of the above approach
using System;
class GFG {
// Function to encode strings as "xAyB"
static string encodeStrings(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 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 += 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;
// Therefore x = same_dig_cnt, y = count.
// Now return the final string as "xAyB"
string ans = "" + same_dig_cnt.ToString() + "A"
+ count.ToString() + "B";
return ans;
}
// Driver code
public static void Main()
{
int N = 1807, M = 7810;
Console.Write("\"" + encodeStrings(N, M) + "\"");
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript code for the above approach
function encodeStrings(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;
// Therefore x = same_dig_cnt, y = count.
// Now return the final string as "xAyB"
let ans = (same_dig_cnt).toString() + "A"
+ (count).toString() + "B";
return ans;
}
// Driver code
let N = 1807, M = 7810;
document.write(`"${encodeStrings(N, M)}"`);
// This code is contributed by Potta Lokesh
</script>
Producción
"1A3B"
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