Recuento de números en el rango donde el primer dígito es igual al último dígito del número

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *