Dado un rango representado por dos números enteros positivos L y R. Encuentra el conteo de números en el rango donde el primer dígito es igual al último dígito del número.
Ejemplos:
Input : L = 2, R = 60 Output : 13 Explanation : Required numbers are 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44 and 55 Input : L = 1, R = 1000 Output : 108
Requisitos previos : Digit DP
Puede haber dos enfoques para resolver este tipo de problema, uno puede ser una solución combinatoria y otros pueden ser una solución basada en programación dinámica. A continuación se muestra un enfoque detallado para resolver este problema utilizando la programación dinámica de dígitos.
Solución de programación dinámica: en primer lugar, si podemos contar los números requeridos hasta R, es decir, en el rango [0, R], podemos llegar fácilmente a nuestra respuesta en el rango [L, R] resolviendo de cero a R y luego restamos la respuesta que obtenemos después de resolver de cero a L – 1. Ahora, necesitamos definir los estados de DP.
Estados DP :
- Dado que podemos considerar nuestro número como una secuencia de dígitos, un estado es la posición en la que nos encontramos actualmente. Esta posición puede tener valores de 0 a 18 si estamos tratando con números hasta 10 18 . En cada llamada recursiva, tratamos de construir la secuencia de izquierda a derecha colocando un dígito del 0 al 9.
- El segundo estado es el firstD que define el primer dígito del número que estamos tratando de construir y puede tener valores de 0 a 9.
- El tercer estado es el lastD que define el último dígito del número que estamos tratando de construir y puede tener valores de 0 a 9.
- Otro estado es la variable booleana tight que indica que el número que estamos tratando de construir ya se ha vuelto más pequeño que R, de modo que en las próximas llamadas recursivas podemos colocar cualquier dígito del 0 al 9. Si el número no se ha vuelto más pequeño, el límite máximo de dígito que podemos colocar es dígito en la posición actual en R.
En cada llamada recursiva, establecemos el último dígito como el dígito que colocamos en la última posición, y establecemos el primer dígito como el primer dígito distinto de cero del número. En la llamada recursiva final, cuando estamos en la última posición si el primer dígito es igual al último dígito, devuelve 1, de lo contrario 0.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ Program to find the count of
// numbers in a range where the number
// does not contain more than K non
// zero digits
#include <bits/stdc++.h>
using namespace std;
const int M = 20;
// states - position, first digit,
// last digit, tight
int dp[M][M][M][2];
// This function returns the count of
// required numbers from 0 to num
int count(int pos, int firstD, int lastD,
int tight, vector<int> num)
{
// Last position
if (pos == num.size()) {
// If first digit is equal to
// last digit
if (firstD == lastD)
return 1;
return 0;
}
// If this result is already computed
// simply return it
if (dp[pos][firstD][lastD][tight] != -1)
return dp[pos][firstD][lastD][tight];
int ans = 0;
// Maximum limit upto which we can place
// digit. If tight is 1, means number has
// already become smaller so we can place
// any digit, otherwise num[pos]
int limit = (tight ? 9 : num[pos]);
for (int dig = 0; dig <= limit; dig++) {
int currFirst = firstD;
// If the position is 0, current
// digit can be first digit
if (pos == 0)
currFirst = dig;
// In current call, if the first
// digit is zero and current digit
// is nonzero, update currFirst
if (!currFirst && dig)
currFirst = dig;
int currTight = tight;
// At this position, number becomes
// smaller
if (dig < num[pos])
currTight = 1;
// Next recursive call, set last
// digit as dig
ans += count(pos + 1, currFirst,
dig, currTight, num);
}
return dp[pos][firstD][lastD][tight] = ans;
}
// This function converts a number into its
// digit vector and uses above function to compute
// the answer
int solve(int x)
{
vector<int> num;
while (x) {
num.push_back(x % 10);
x /= 10;
}
reverse(num.begin(), num.end());
// Initialize dp
memset(dp, -1, sizeof(dp));
return count(0, 0, 0, 0, num);
}
// Driver Code
int main()
{
int L = 2, R = 60;
cout << solve(R) - solve(L - 1) << endl;
L = 1, R = 1000;
cout << solve(R) - solve(L - 1) << endl;
return 0;
}
Java
// Java program to find the count of
// numbers in a range where the number
// does not contain more than K non
// zero digits
import java.util.Collections;
import java.util.Vector;
class GFG
{
static int M = 20;
// states - position, first digit,
// last digit, tight
static int[][][][] dp = new int[M][M][M][2];
// This function returns the count of
// required numbers from 0 to num
static int count(int pos, int firstD,
int lastD, int tight,
Vector<Integer> num)
{
// Last position
if (pos == num.size())
{
// If first digit is equal to
// last digit
if (firstD == lastD)
return 1;
return 0;
}
// If this result is already computed
// simply return it
if (dp[pos][firstD][lastD][tight] != -1)
return dp[pos][firstD][lastD][tight];
int ans = 0;
// Maximum limit upto which we can place
// digit. If tight is 1, means number has
// already become smaller so we can place
// any digit, otherwise num[pos]
int limit = (tight == 1 ? 9 : num.elementAt(pos));
for (int dig = 0; dig <= limit; dig++)
{
int currFirst = firstD;
// If the position is 0, current
// digit can be first digit
if (pos == 0)
currFirst = dig;
// In current call, if the first
// digit is zero and current digit
// is nonzero, update currFirst
if (currFirst == 0 && dig != 0)
currFirst = dig;
int currTight = tight;
// At this position, number becomes
// smaller
if (dig < num.elementAt(pos))
currTight = 1;
// Next recursive call, set last
// digit as dig
ans += count(pos + 1, currFirst,
dig, currTight, num);
}
return dp[pos][firstD][lastD][tight] = ans;
}
// This function converts a number into its
// digit vector and uses above function to
// compute the answer
static int solve(int x)
{
Vector<Integer> num = new Vector<>();
while (x > 0)
{
num.add(x % 10);
x /= 10;
}
Collections.reverse(num);
// Initialize dp
for (int i = 0; i < M; i++)
for (int j = 0; j < M; j++)
for (int k = 0; k < M; k++)
for (int l = 0; l < 2; l++)
dp[i][j][k][l] = -1;
return count(0, 0, 0, 0, num);
}
// Driver Code
public static void main(String[] args)
{
int L = 2, R = 60;
System.out.println(solve(R) - solve(L - 1));
L = 1;
R = 1000;
System.out.println(solve(R) - solve(L - 1));
}
}
// This code is contributed by
// sanjeev2552
Python3
# Python3 code for above approach # Returns the count of numbers in range # if the first digit is equal to last digit of number def count(l, r): cnt = 0 # Initialize counter for i in range(l, r): # If number is less than 10 # then increment counter # as number has only one digit if(i < 10): cnt += 1 else: n = i % 10 # Find the last digit k = i # Find the first digit while(k >= 10): k = k // 10 # If first digit equals last digit # then increment counter if(n == k): cnt += 1 return(cnt) # Return the count # Driver Code L = 2; R = 60; print(count(L, R)) L = 1; R = 1000; print(count(L, R)) # This code is contributed by Raj
C#
// C# program to find the count of
// numbers in a range where the number
// does not contain more than K non
// zero digits
using System;
using System.Collections.Generic;
class GFG
{
static int M = 20;
// states - position, first digit,
// last digit, tight
static int[,,,] dp = new int[M, M, M, 2];
// This function returns the count of
// required numbers from 0 to num
static int count(int pos, int firstD,
int lastD, int tight,
List<int> num)
{
// Last position
if (pos == num.Count)
{
// If first digit is equal to
// last digit
if (firstD == lastD)
return 1;
return 0;
}
// If this result is already computed
// simply return it
if (dp[pos, firstD, lastD, tight] != -1)
return dp[pos, firstD, lastD, tight];
int ans = 0;
// Maximum limit upto which we can place
// digit. If tight is 1, means number has
// already become smaller so we can place
// any digit, otherwise num[pos]
int limit = (tight == 1 ? 9 : num[pos]);
for (int dig = 0; dig <= limit; dig++)
{
int currFirst = firstD;
// If the position is 0, current
// digit can be first digit
if (pos == 0)
currFirst = dig;
// In current call, if the first
// digit is zero and current digit
// is nonzero, update currFirst
if (currFirst == 0 && dig != 0)
currFirst = dig;
int currTight = tight;
// At this position, number becomes
// smaller
if (dig < num[pos])
currTight = 1;
// Next recursive call, set last
// digit as dig
ans += count(pos + 1, currFirst,
dig, currTight, num);
}
return dp[pos, firstD, lastD, tight] = ans;
}
// This function converts a number into its
// digit vector and uses above function to
// compute the answer
static int solve(int x)
{
List<int> num = new List<int>();
while (x > 0)
{
num.Add(x % 10);
x /= 10;
}
num.Reverse();
// Initialize dp
for (int i = 0; i < M; i++)
for (int j = 0; j < M; j++)
for (int k = 0; k < M; k++)
for (int l = 0; l < 2; l++)
dp[i, j, k, l] = -1;
return count(0, 0, 0, 0, num);
}
// Driver Code
public static void Main(String[] args)
{
int L = 2, R = 60;
Console.WriteLine(solve(R) - solve(L - 1));
L = 1;
R = 1000;
Console.WriteLine(solve(R) - solve(L - 1));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to find the count of
// numbers in a range where the number
// does not contain more than K non
// zero digits
let M = 20;
// states - position, first digit,
// last digit, tight
let dp = new Array(M);
for(let i=0;i<M;i++)
{
dp[i]=new Array(M);
for(let j=0;j<M;j++)
{
dp[i][j]=new Array(M);
for(let k=0;k<M;k++)
dp[i][j][k]=new Array(2);
}
}
// This function returns the count of
// required numbers from 0 to num
function count(pos,firstD,lastD,tight, num)
{
// Last position
if (pos == num.length)
{
// If first digit is equal to
// last digit
if (firstD == lastD)
return 1;
return 0;
}
// If this result is already computed
// simply return it
if (dp[pos][firstD][lastD][tight] != -1)
return dp[pos][firstD][lastD][tight];
let ans = 0;
// Maximum limit upto which we can place
// digit. If tight is 1, means number has
// already become smaller so we can place
// any digit, otherwise num[pos]
let limit = (tight == 1 ? 9 : num[pos]);
for (let dig = 0; dig <= limit; dig++)
{
let currFirst = firstD;
// If the position is 0, current
// digit can be first digit
if (pos == 0)
currFirst = dig;
// In current call, if the first
// digit is zero and current digit
// is nonzero, update currFirst
if (currFirst == 0 && dig != 0)
currFirst = dig;
let currTight = tight;
// At this position, number becomes
// smaller
if (dig < num[pos])
currTight = 1;
// Next recursive call, set last
// digit as dig
ans += count(pos + 1, currFirst,
dig, currTight, num);
}
return dp[pos][firstD][lastD][tight] = ans;
}
// This function converts a number into its
// digit vector and uses above function to
// compute the answer
function solve(x)
{
let num = [];
while (x > 0)
{
num.push(x % 10);
x = Math.floor(x/10);
}
num.reverse();
// Initialize dp
for (let i = 0; i < M; i++)
for (let j = 0; j < M; j++)
for (let k = 0; k < M; k++)
for (let l = 0; l < 2; l++)
dp[i][j][k][l] = -1;
return count(0, 0, 0, 0, num);
}
// Driver Code
let L = 2, R = 60;
document.write(solve(R) - solve(L - 1)+"<br>");
L = 1;
R = 1000;
document.write(solve(R) - solve(L - 1)+"<br>");
// This code is contributed by rag2127
</script>
Producción
13 108
Complejidad Temporal: O(18 * 10 * 10 * 2 * 10), si se trata de números hasta 10 18
Espacio Auxiliar: O(20*20*20*2).
Enfoque alternativo:
También podemos resolver este problema por recursión, para cada posición podemos llenar cualquier número que satisfaga la condición dada excepto por la primera y la última posición porque estarán emparejadas, y para esto, usaremos la recursión y en cada llamada solo verifica si el primer número es menor o mayor que el último número, si resulta ser mayor que sumaremos 8; de lo contrario, 9 y pediremos el número / 10, una vez que el número sea menor que 10 primero y el último dígito sea el mismo, devuelva el número en sí.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to implement
// the above approach
#include <iostream>
using namespace std;
int solve(int x)
{
int ans = 0, first, last, temp = x;
// Base Case
if (x < 10)
return x;
// Calculating the last digit
last = x % 10;
// Calculating the first digit
while (x) {
first = x % 10;
x /= 10;
}
if (first <= last)
ans = 9 + temp / 10;
else
ans = 8 + temp / 10;
return ans;
}
// Drivers Code
int main()
{
int L = 2, R = 60;
cout << solve(R) - solve(L - 1) << endl;
L = 1, R = 1000;
cout << solve(R) - solve(L - 1) << endl;
return 0;
}
Java
// Java program to implement
// the above approach
class GFG{
public static int solve(int x)
{
int ans = 0, first = 0,
last, temp = x;
// Base Case
if (x < 10)
return x;
// Calculating the
// last digit
last = x % 10;
// Calculating the
// first digit
while (x != 0)
{
first = x % 10;
x /= 10;
}
if (first <= last)
ans = 9 + temp / 10;
else
ans = 8 + temp / 10;
return ans;
}
// Driver code
public static void main(String[] args)
{
int L = 2, R = 60;
System.out.println(solve(R) -
solve(L - 1));
L = 1; R = 1000;
System.out.println(solve(R) -
solve(L - 1));
}
}
// This code is contributed by divyeshrabadiya07
Python3
# Python3 program to implement # the above approach def solve(x): ans, temp = 0, x # Base Case if (x < 10): return x # Calculating the last digit last = x % 10 # Calculating the first digit while (x): first = x % 10 x = x // 10 if (first <= last): ans = 9 + temp // 10 else: ans = 8 + temp // 10 return ans # Driver Code L, R = 2, 60 print(solve(R) - solve(L - 1)) L, R = 1, 1000 print(solve(R) - solve(L - 1)) # This code is contributed by divyesh072019
C#
// C# program to implement
// the above approach
using System;
class GFG{
public static int solve(int x)
{
int ans = 0, first = 0,
last, temp = x;
// Base Case
if (x < 10)
return x;
// Calculating the
// last digit
last = x % 10;
// Calculating the
// first digit
while (x != 0)
{
first = x % 10;
x /= 10;
}
if (first <= last)
ans = 9 + temp / 10;
else
ans = 8 + temp / 10;
return ans;
}
// Driver code
public static void Main(String[] args)
{
int L = 2, R = 60;
Console.WriteLine(solve(R) -
solve(L - 1));
L = 1; R = 1000;
Console.WriteLine(solve(R) -
solve(L - 1));
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
// Javascript program to implement
// the above approach
function solve(x)
{
let ans = 0, first, last, temp = x;
// Base Case
if (x < 10)
return x;
// Calculating the last digit
last = x % 10;
// Calculating the first digit
while (x > 0)
{
first = x % 10;
x /= 10;
}
if (first <= last)
ans = 9 + temp / 10;
else
ans = 8 + temp / 10;
return ans;
}
let L = 2, R = 60;
document.write((solve(R) - solve(L - 1)) + "</br>");
L = 1, R = 1000;
document.write(solve(R) - solve(L - 1));
// This code is contributed by suresh07.
</script>
Producción
13 108
Complejidad de tiempo: O(log 10 (max(L,R))).
Espacio Auxiliar: O(1).
Publicación traducida automáticamente
Artículo escrito por Nishant Tanwar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA