Dado un rango en la forma de L y R , y un valor K , la tarea es contar los números entre el rango L a R tal que la suma del dígito sea divisible por K , y el primer dígito no sea igual al último dígito del número.
Ejemplos:
Entrada: L = 1, R = 10, K = 2
Salida: 0
Explicación:
Los números de entrada cuya suma de dígitos es divisible por 2 (K = 2) son 2, 4, 6, 8 pero el primer dígito de todos estos números es igual a la última cifra. Por lo tanto, la respuesta es 0, lo que significa que ninguno de los dígitos cumple la condición.Entrada: L = 10, R = 20, K = 2
Salida: 5
Explicación:
Los números cuya suma de dígitos es divisible por 2 (K = 2) son 11, 13, 15, 17, 19 y 20. Pero en 11 el primer dígito coincide con el último dígito. Así que excluyendo esto, la respuesta será 5.
Enfoque ingenuo:
el enfoque ingenuo para resolver este problema es verificar cada número si cumple o no la condición dada. Sin embargo, esta solución funcionará de manera ineficiente debido al rango de números.
Enfoque eficiente:
la idea principal para resolver este problema es utilizar la programación dinámica de dígitos .
Hay varios estados que deben definirse para la transición. Entonces, podemos definir los estados de DP como:
- Dado que en digit DP, pensamos que un número es una secuencia de dígitos , por lo que para atravesar la secuencia, necesitamos la posición como estado. Lo que generalmente hacemos es colocar todos los dígitos posibles [0, 9] en la llamada recursiva, que podemos colocar en cada posición para encontrar una posible solución siempre que se cumplan todas las condiciones.
- Lo segundo que necesitamos es la suma, con la que hemos construido nuestra secuencia. Dado que la suma puede ser grande, podemos mantener la suma como suma módulo K para una mejor complejidad de espacio y tiempo. Entonces la suma es el segundo estado DP.
- Lo tercero que necesitamos es el dígito , que hemos colocado en la primera posición . Mientras colocamos el último dígito de la secuencia, debemos verificar si es igual al primer dígito, que hemos colocado anteriormente o no. Entonces, este será el tercer estado de DP.
- El problema es que cada vez que creamos una secuencia de N dígitos, donde N es el número de dígitos presentes en el límite superior del número, no crea 1 si (N=3), pero crea 001. Aquí el el primer dígito es 0 y el último dígito es 1, pero esto es incorrecto ya que hemos creado un número de un solo dígito cuyo primer dígito es igual al último dígito. Entonces, tenemos que verificar esto cada vez en la llamada recursiva. Supongamos que tenemos que construir una secuencia como 0002 donde necesitamos actualizar nuestro dígito inicial igual a 2. Por lo tanto, se debe ignorar un prefijo de ceros. Para verificar esto, necesitamos un nuevo estado booleano (0 o 1) . Este es el cuarto estado DP.
- Lo último que necesitamos es verificar si el número que estamos construyendo no excede el límite superior . Supongamos que estamos construyendo un número menor que igual a 456. Hemos creado una secuencia como 45, por lo que en el tercer lugar, no podemos poner ningún dígito entre 0 y 9. Aquí solo podemos colocar números del 0 al 6. Entonces, para verificar este límite, necesitamos un estado booleano adicional . Este es nuestro último estado DP.
Algoritmo:
- En cada posición, calculamos la suma de dígitos y eliminamos el prefijo de ceros.
- El primer dígito distinto de cero será nuestro dígito inicial de la secuencia.
- En la última posición, comprobaremos si coincide con el dígito inicial o no.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ Program to count numbers
// in a range with digit sum
// divisible by K having first
// and last digit different
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
ll K;
ll N;
vector<int> v;
ll dp[20][1000][10][2][2];
void init(ll x)
{
memset(dp, -1, sizeof(dp));
// For calculating the upper
// bound of the sequence.
v.clear();
while (x > 0) {
v.push_back(x % 10);
x /= 10;
}
reverse(v.begin(), v.end());
N = v.size();
}
ll fun(ll pos, ll sum, ll st, ll check, ll f)
{
if (pos == N) {
// checking whether the sum
// of digits = 0 or not
// and the corner case
// as number equal to 1
return (sum == 0
and check == 1);
}
// If the state is visited
// then return the answer
// of this state directly.
if (dp[pos][sum][st][check][f] != -1)
return dp[pos][sum][st][check][f];
ll lmt = 9;
// for checking whether digit
// to be placed is up to
// upper bound at the
// position pos or upto 9
if (!f)
lmt = v[pos];
ll ans = 0;
for (int digit = 0; digit <= lmt; digit++) {
ll nf = f;
// calculating new digit
// sum modulo k
ll new_sum = (sum + digit) % K;
ll new_check = check;
ll new_st = st;
if (f == 0 and digit < lmt)
nf = 1;
// check if there is a prefix
// of 0s and current digit != 0
if (check == 0 and digit != 0) {
// Then current digit will
// be the starting digit
new_st = digit;
// Update the boolean flag
// that the starting digit
// has been found
new_check = 1;
}
// At n-1, check if current digit
// and starting digit are the same
// then no need to calculate this answer.
if (pos == N - 1
and new_st == digit)
continue;
// Else find the answer
ans += fun(pos + 1,
new_sum,
new_st,
new_check, nf);
}
return dp[pos][sum][st][check][f] = ans;
}
// Function to find the required count
void findCount(int L, int R, int K)
{
// Setting up the upper bound
init(R);
// calculating F(R)
ll r_ans = fun(0, 0, 0, 0, 0);
// Setting up the upper bound
init(L - 1);
// calculating F(L-1)
ll l_ans = fun(0, 0, 0, 0, 0);
cout << r_ans - l_ans;
}
// Driver code
int main()
{
ll L = 10;
ll R = 20;
K = 2;
findCount(L, R, K);
return 0;
}
Java
// Java Program to count numbers
// in a range with digit sum
// divisible by K having first
// and last digit different
import java.util.*;
class GFG{
static int K;
static int N;
static Vector<Integer> v = new Vector<>();
static int [][][][][]dp = new int[20][1000][10][2][2];
static void init(int x)
{
for(int i = 0; i < 20; i++)
for(int j = 0; j < 1000; j++)
for(int k = 0; k < 10; k++)
for(int l = 0; l < 2; l++)
for(int m = 0; m < 2; m++)
dp[i][j][k][l][m] = -1;
// For calculating the upper
// bound of the sequence.
v.clear();
while (x > 0)
{
v.add(x % 10);
x /= 10;
}
Collections.reverse(v);
N = v.size();
}
static int fun(int pos, int sum,
int st, int check, int f)
{
if (pos == N)
{
// checking whether the sum
// of digits = 0 or not
// and the corner case
// as number equal to 1
return (sum == 0 && check == 1) ? 1 : 0;
}
// If the state is visited
// then return the answer
// of this state directly.
if (dp[pos][sum][st][check][f] != -1)
return dp[pos][sum][st][check][f];
int lmt = 9;
// for checking whether digit
// to be placed is up to
// upper bound at the
// position pos or upto 9
if (f == 0)
lmt = v.get(pos);
int ans = 0;
for (int digit = 0; digit <= lmt; digit++)
{
int nf = f;
// calculating new digit
// sum modulo k
int new_sum = (sum + digit) % K;
int new_check = check;
int new_st = st;
if (f == 0 && digit < lmt)
nf = 1;
// check if there is a prefix
// of 0s and current digit != 0
if (check == 0 && digit != 0)
{
// Then current digit will
// be the starting digit
new_st = digit;
// Update the boolean flag
// that the starting digit
// has been found
new_check = 1;
}
// At n-1, check if current digit
// and starting digit are the same
// then no need to calculate this answer.
if (pos == N - 1 && new_st == digit)
continue;
// Else find the answer
ans += fun(pos + 1, new_sum,
new_st, new_check, nf);
}
return dp[pos][sum][st][check][f] = ans;
}
// Function to find the required count
static void findCount(int L, int R, int K)
{
// Setting up the upper bound
init(R);
// calculating F(R)
int r_ans = fun(0, 0, 0, 0, 0);
// Setting up the upper bound
init(L - 1);
// calculating F(L-1)
int l_ans = fun(0, 0, 0, 0, 0);
System.out.print(r_ans - l_ans);
}
// Driver code
public static void main(String[] args)
{
int L = 10;
int R = 20;
K = 2;
findCount(L, R, K);
}
}
// This code contributed by PrinciRaj1992
Python3
# Python3 program to count numbers # in a range with digit sum # divisible by K having first # and last digit different K = 0 N = 0 v = [] dp = [[[[[-1 for i in range(2)] for j in range(2)] for k in range(10)] for l in range(1000)] for m in range(20)] def init(x): # For calculating the upper # bound of the sequence. global K global N global v v = [] while (x > 0): v.append(x % 10) x //= 10 v = v[::-1] N = len(v) def fun(pos, sum, st, check, f): global N global v if (pos == N): # Checking whether the sum of # digits = 0 or not and the # corner case as number equal to 1 return (sum == 0 and check == 1) # If the state is visited # then return the answer # of this state directly. if (dp[pos][sum][st][check][f] != -1): return dp[pos][sum][st][check][f] lmt = 9 # For checking whether digit to # be placed is up to upper bound # at the position pos or upto 9 if (f == False): lmt = v[pos] ans = 0 for digit in range(lmt + 1): nf = f # Calculating new digit # sum modulo k new_sum = (sum + digit) % K new_check = check new_st = st if (f == 0 and digit < lmt): nf = 1 # Check if there is a prefix # of 0s and current digit != 0 if (check == 0 and digit != 0): # Then current digit will # be the starting digit new_st = digit # Update the boolean flag # that the starting digit # has been found new_check = 1 # At n-1, check if current digit # and starting digit are the same # then no need to calculate this answer if (pos == N - 1 and new_st == digit): continue # Else find the answer ans += fun(pos + 1, new_sum, new_st, new_check, nf) dp[pos][sum][st][check][f] = ans return ans # Function to find the required count def findCount(L, R, K): # Setting up the upper bound init(R) # calculating F(R) r_ans = fun(0, 0, 0, 0, 0) # Setting up the upper bound init(L - 1) # Calculating F(L-1) r_ans = 0 l_ans = fun(0, 0, 0, 0, 0) print(l_ans - r_ans) # Driver code if __name__ == '__main__': L = 10 R = 20 K = 2 findCount(L, R, K) # This code is contributed by Surendra_Gangwar
C#
// C# program to count numbers
// in a range with digit sum
// divisible by K having first
// and last digit different
using System;
using System.Collections.Generic;
class GFG{
static int K;
static int N;
static List<int> v = new List<int>();
static int [,,,,]dp = new int[20, 1000, 10, 2, 2];
static void init(int x)
{
for(int i = 0; i < 20; i++)
for(int j = 0; j < 1000; j++)
for(int k = 0; k < 10; k++)
for(int l = 0; l < 2; l++)
for(int m = 0; m < 2; m++)
dp[i, j, k, l, m] = -1;
// For calculating the upper
// bound of the sequence.
v.Clear();
while (x > 0)
{
v.Add(x % 10);
x /= 10;
}
v.Reverse();
N = v.Count;
}
static int fun(int pos, int sum, int st,
int check, int f)
{
if (pos == N)
{
// Checking whether the sum
// of digits = 0 or not
// and the corner case
// as number equal to 1
return (sum == 0 && check == 1) ? 1 : 0;
}
// If the state is visited
// then return the answer
// of this state directly.
if (dp[pos, sum, st, check, f] != -1)
return dp[pos, sum, st, check, f];
int lmt = 9;
// For checking whether digit
// to be placed is up to
// upper bound at the
// position pos or upto 9
if (f == 0)
lmt = v[pos];
int ans = 0;
for(int digit = 0; digit <= lmt; digit++)
{
int nf = f;
// Calculating new digit
// sum modulo k
int new_sum = (sum + digit) % K;
int new_check = check;
int new_st = st;
if (f == 0 && digit < lmt)
nf = 1;
// Check if there is a prefix
// of 0s and current digit != 0
if (check == 0 && digit != 0)
{
// Then current digit will
// be the starting digit
new_st = digit;
// Update the bool flag
// that the starting digit
// has been found
new_check = 1;
}
// At n-1, check if current digit
// and starting digit are the same
// then no need to calculate this answer.
if (pos == N - 1 && new_st == digit)
continue;
// Else find the answer
ans += fun(pos + 1, new_sum,
new_st, new_check, nf);
}
return dp[pos, sum, st, check, f] = ans;
}
// Function to find the required count
static void findCount(int L, int R, int K)
{
// Setting up the upper bound
init(R);
// Calculating F(R)
int r_ans = fun(0, 0, 0, 0, 0);
// Setting up the upper bound
init(L - 1);
// calculating F(L-1)
int l_ans = fun(0, 0, 0, 0, 0);
Console.Write(r_ans - l_ans);
}
// Driver code
public static void Main(String[] args)
{
int L = 10;
int R = 20;
K = 2;
findCount(L, R, K);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to count numbers
// in a range with digit sum
// divisible by K having first
// and last digit different
var K;
var N;
var v = [];
var dp = Array.from(Array(20));
function init( x)
{
for(var i = 0; i< 20;i++)
{
dp[i] = Array.from(Array(1000),()=>Array(10));
for(var j =0; j<1000;j++)
{
for(var k = 0; k<10;k++)
{
dp[i][j][k] = Array.from(Array(2), ()=>Array(2).fill(-1));
}
}
}
// For calculating the upper
// bound of the sequence.
v = [];
while (x > 0)
{
v.push(x % 10);
x = parseInt(x/10);
}
v.reverse();
N = v.length;
}
function fun(pos, sum, st, check, f)
{
if (pos == N)
{
// Checking whether the sum
// of digits = 0 or not
// and the corner case
// as number equal to 1
return (sum == 0 && check == 1) ? 1 : 0;
}
// If the state is visited
// then return the answer
// of this state directly.
if (dp[pos][sum][st][check][f] != -1)
return dp[pos][sum][st][check][f];
var lmt = 9;
// For checking whether digit
// to be placed is up to
// upper bound at the
// position pos or upto 9
if (f == 0)
lmt = v[pos];
var ans = 0;
for(var digit = 0; digit <= lmt; digit++)
{
var nf = f;
// Calculating new digit
// sum modulo k
var new_sum = (sum + digit) % K;
var new_check = check;
var new_st = st;
if (f == 0 && digit < lmt)
nf = 1;
// Check if there is a prefix
// of 0s and current digit != 0
if (check == 0 && digit != 0)
{
// Then current digit will
// be the starting digit
new_st = digit;
// Update the bool flag
// that the starting digit
// has been found
new_check = 1;
}
// At n-1, check if current digit
// and starting digit are the same
// then no need to calculate this answer.
if (pos == N - 1 && new_st == digit)
continue;
// Else find the answer
ans += fun(pos + 1, new_sum,
new_st, new_check, nf);
}
return dp[pos][sum][st][check][f] = ans;
}
// Function to find the required count
function findCount(L, R, K)
{
// Setting up the upper bound
init(R);
// Calculating F(R)
var r_ans = fun(0, 0, 0, 0, 0);
// Setting up the upper bound
init(L - 1);
// calculating F(L-1)
var l_ans = fun(0, 0, 0, 0, 0);
document.write(r_ans - l_ans);
}
// Driver code
var L = 10;
var R = 20;
K = 2;
findCount(L, R, K);
// This code is contributed by itsok.
</script>
Producción:
5
Complejidad de tiempo: O(18*1000*10*2*2), que es casi O(2*10^6) .
Espacio auxiliar: O(800*1000)