Pre-requisitos: Recursividad , Programación Dinámica , Digit DP
Dado un entero Y y un rango [L, R] , la tarea es encontrar el conteo de todos los números del rango dado cuya suma de dígitos es igual a Y .
Ejemplos:
Entrada: L = 0, R = 11, Y = 2
Salida: 2
2 -> 2
11 -> 1 + 1 = 2
Entrada: L = 500, R = 1000, Y = 6
Salida: 3
Restricciones:
0 <= L <= R <= 10^18
0 <= Y <= 162 (Que es la suma máxima posible que puede tener un número de 18 dígitos)
Enfoque: En primer lugar, generalizando la pregunta, [L, R] se puede escribir como [0, R] – [0, L-1], es decir, encontrando primero todos los números en el rango [0, R] cuya suma de dígitos = Y, y luego para el rango [0, L-1], luego finalmente restando cada valor para obtener el resultado deseado. Entonces, para el caso del dígito, almacenemos los dígitos del número L y R en 2 vectores separados para que sea más fácil acceder a su dígito. Entonces necesitamos una función que lleve (índice_actual, bandera, suma). Esta función es la parte principal de nuestra lógica. Inicializando índice_actual = 0, bandera = 0, suma = 0.
Digamos R = 462, este número tiene 3 índices, es decir, 0, 1, 2. Ahora comprueba de cuántas maneras puedes llenar el índice 0. En la observación podemos decir que podemos llenar el índice 0 como 0, 1, 2, 3 y 4. Si excedemos de 4, entonces formaríamos un número mayor que 462.
Ahora, si ha insertado 0 en el índice 0, ¿cuál puede ser la posibilidad para el índice 1? Respuesta: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Dado que tiene un número 0 en el índice 0, puede completar cualquier número del 0 al 9 en el índice 1. De acuerdo, como puede completar cualquier número en el siguiente índice, cambiará flag = 1. flag = 1 díganos que tenemos la ventaja de completar cualquier cosa del 0 al 9. Del mismo modo, pensando en los otros índices.
Ahora si vemos la condición base
if(índice_actual == n) {
if(suma == Y) devuelve 1;
de lo contrario devuelve 0;
}
A continuación se muestra la implementación del enfoque anterior:
C++
#include<bits/stdc++.h>
using namespace std;
// function to convert digit to vector
vector<int> digitToVec(int n) {
vector<int> a;
while (n) {
a.push_back(n % 10);
n = n / 10;
}
reverse(a.begin(), a.end());
return a;
}
int Y; // setting Y as global
int dp[19][2][18 * 9 + 1]; // 3D dp
int func(int ind, int flag, int sum, vector<int> a) {
if (ind == a.size()) {
if (sum == Y) return 1;
else return 0;
}
if (dp[ind][flag][sum] != -1) return dp[ind][flag][sum];
// if flag = 0, I know I can only fill from 0 to a[ind]
// if flag = 1, I have the advantage to fill from 0 to 9
int limit = 9;
if (flag == 0) limit = a[ind];
int cnt = 0;
for (int num = 0; num <= limit; num++) {
// if flag = 0, which means no advantage
// and I am still filling the same number as a[ind] means giving him no advantage
// hence the next recursion call flag still stays as 0
if (flag == 0 && num == a[ind]) {
cnt += func(ind + 1, 0, sum + num, a);
}
else {
cnt += func(ind + 1, 1, sum + num, a);
}
}
return dp[ind][flag][sum] = cnt;
}
// intermediate function helping to initialize all values of func()
int ans(int n) {
vector<int> a = digitToVec(n);
memset(dp, -1, sizeof dp); // initializing dp as -1
return func(0, 0, 0, a);
}
// Driver code
int main() {
int l, r;
cin >> l >> r >> Y;
cout << ans(r) - ans(l - 1);
return 0;
}
2
Ahora hablando del peor de los casos Complejidad del tiempo: O(19 * 2 * (18 * 9) * 10)