Find the Count of Good Integers

En este artículo, vamos a resolver un problema muy interesante que ha sido preguntado recientemente en entrevistas de código en Google y Meta este año (Link al problema).

A pesar de estar clasificado como “Hard” en Leetcode, es un problema sumamente instructivo, ideal para reforzar habilidades en fuerza bruta optimizada y razonamiento combinatorio.

Acompáñame paso a paso: analizaremos su estructura, entenderemos por qué las soluciones ingenuas fallan y construiremos una estrategia eficiente basada en observaciones clave y conteo inteligente.

Enunciado del problema

Un entero $x$ es llamado $k-$palindrómico si:

• $x$ es palíndromo.
• $x$ es divisible por $k$.

Un número $x$ es llamado bueno, si puedes reordenar sus dígitos para formar un número $k-$palindrómico.

Queremos encontrar la cantidad de números de $n$ cifras que son buenos.

Nota: Ningún entero debe contener ceros al inicio, ni antes ni después del reordenamiento.

Las restricciones del problema:

• $1\le n\le 10$
• $1\le k\le 9$

Iterar sobre todos los números de $n$ dígitos

Un primer acercamiento sería probar con todos los números de $n$ dígitos y verificar las dos condiciones.

• Cantidad de números de $n$ dígitos:
  $$9 \times 10 ^{n-1}$$
  Para $n=10$, esta solución nos llevaría a un TLE (Time Limit Exceeded).
  Por tanto, necesitamos una forma más inteligente de reducir el espacio de búsqueda

Iterar sobre todos los palíndromos

La observación fundamental es que el requisito de "poder formar un palíndromo" limita fuertemente los dígitos posibles.
En lugar de iterar sobre todos los números, podemos generar directamente palíndromos:

• Un palíndromo de $n$ dígitos está completamente determinado por su primera mitad.
• Eso significa que en lugar de $10^n$ candidatos, solo tenemos que considerar $10^{\lceil{n/2}\rceil}$.

Ejemplo

• Si $n=6$, un palíndromo está definido por sus 3 primeros dígitos.
  • La mitad $=123$ genera el palíndromo $123321$.
• Si $n=5$, un palíndromo está definido por 3 dígitos, pero el del medio no se espeja.
  • La mitad $=123$ genera el palíndromo $12321$.

Esto reduce enormemente la complejidad.

Con esto, podemos iterar sobre cada uno de estos palíndromos y realizamos lo siguiente:

1. Verificamos que sea divisible por $k$. Si no lo es, descartamos el palíndromo.
2. Calculamos la cantidad de permutaciones de sus dígitos (todos estos números son buenos).
3. Evitar contar duplicados. Por ejemplo, si anteriormente ya se añadieron las permutaciones de $1221$, no añadir las permutaciones de $2112$, puesto que generan los mismos números y por tanto se está duplicando los resultados.
4. Si no es duplicado, añadimos esta cantidad a la respuesta final.

Retornamos la suma obtenida como respuesta final.

Calcular la cantidad de permutaciones de los dígitos

Dado un número, primero calculamos la frecuencia de cada dígito. Llamemos $d_i$ la cantidad de dígitos $i$ que existen en el número, para todo $0 \le i \le 9$. Entonces, la cantidad de permutaciones de los dígitos será igual a:
$$\frac{(d_0+d_1+\cdots+d_9)!}{d_0!\cdot d_1!\cdots d_9!}$$
Como la cantidad máxima de dígitos es $n=10$, podemos precomputar el factorial de $0,1,\cdots,10$.
En código:

long long permutations(vector<int> d) {
	// factorial[i]: precomputamos el factorial de "i"
	int total = 0;
	for(int i = 0; i < 10; i++)
		total += d[i];
	long long ans = factorial[total];
	for(int i = 0; i < 10; i++) {
		ans /= factorial[d[i]];
	}
	return ans;
}

Aún nos falta tener en cuenta la nota del problema: los números no pueden contener ceros iniciales. Por ejemplo, si el palíndromo es $101$, cuando calculamos la cantidad de permutaciones de sus dígitos, también estamos contando al $011$, lo cual no es correcto.

Para resolver esto, tenemos que restar a la cantidad total de permutaciones, todas las permutaciones que inicien en cero. Podemos contar esa cantidad de permutaciones de la siguiente manera:

1. Fijamos un cero al inicio del número, por lo que restamos en $1$ a la frecuencia de cero.
2. Calculamos la cantidad de permutaciones de los dígitos restantes.

En código:

long long valid_permutations = permutations(d);

if(d[0] > 0) {
	// Si encontramos que el paíndromo contiene ceros,
	// entonces restamos uno a la frecuencia de cero.
	d[0]--;
	// Finalmente, restamos esta cantidad a la permutaciones iniciales
	valid_permutations -= permutations(cnt);
}

Evitar duplicados

Como ya mencionamos, debemos de tener cuidado en duplicar los resultados. Por ejemplo, si ya hemos añadido las permutaciones de $1221$, añadir las permutaciones de $2112$ generaría duplicados. Para evitar los duplicados, haremos lo siguiente:

1. Creamos un conjunto vacío.
2. Para cada nuevo palíndromo, ordenamos sus dígitos de menor a mayor (podemos convertirlo a string y ordenar sus dígitos).
3. Verificamos si se encuentra dentro del conjunto vacío. Si está, se descarta. En otro caso, no es duplicado y podemos añadir sus permutaciones a la respuesta final. Y lo añadimos al conjunto para evitar duplicados futuros.

Implementación modelo

Finalmente, agrupando todas las ideas, dejo un ejemplo de implementación:

class Solution {
public:
    int f[11];
    int cd(int n) {
        int cnt = 0;
        while(n != 0) {
            cnt++;
            n /= 10;
        }
        return cnt;
    }
    int reverse(int n) {
        int rev = 0;
        while(n != 0) {
            int d = n % 10;
            rev = rev * 10 + d;
            n /= 10;
        }
        return rev;
    }
    long long permutations(vector<int>& cnt) {
        int total = 0;
        for(int i = 0; i < 10; i++) total += cnt[i];
        long long ans = f[total];
        for(int i = 0; i < 10; i++)
            ans /= f[cnt[i]];
        return ans;
    }
    long long countGoodIntegers(int n, int k) {
        f[0] = 1;
        for(int i = 1; i <= 10; i++) f[i] = i * f[i-1];
        
        int lmt = 1;
        for(int i = 0; i < (n+1)/2; i++) lmt *= 10;
        
        int p = 1;
        for(int i = 0; i < n/2; i++) p *= 10;

        set<string> used;
        int ans = 0;
        
        for(int i = 0; i < lmt; i++) {
            if(cd(i) != (n+1)/2) continue;
            int rev;
            
            if(n % 2 == 0) rev = reverse(i);
            else rev = reverse(i / 10);
            
            long long num = i * 1ll * p + rev;
            if(num % k != 0) continue;
            
            string snum = to_string(num);
            sort(snum.begin(), snum.end());
            if(used.count(snum)) {
                continue;
            }
            
            used.insert(snum);
            vector<int> cnt(10, 0);
            while(num) {
                cnt[num % 10]++;
                num /= 10;
            }
            long long curr = permutations(cnt);
            if(cnt[0] > 0) {
                cnt[0]--;
                curr -= permutations(cnt);
            }
            ans += curr;
        }
        return ans;
    }
};

Esta solución tiene complejidad $\mathcal{O}(10 ^ {\lceil n/2\rceil} \cdot n ^ 2)$ en tiempo.