Recuento de todos los números posibles que no excedan M con el sufijo N

Dados dos enteros positivos N y M , la tarea es encontrar el conteo de todos los números posibles en el rango [1, M] , con el sufijo N .

Ejemplos:

Entrada: N = 5, M = 15 
Salida: 2 
Explicación: Solo los números que cumplen las condiciones son {5, 15}.
Entrada: N = 25, M = 4500 
Salida : 45

Enfoque ingenuo: el enfoque más simple es recorrer todos los enteros en el rango [1, M] y verificar si el sufijo es N o no. 
Tiempo Complejidad: O(M) 
Espacio Auxiliar: O(1)

Enfoque eficiente: Para optimizar el enfoque anterior, es necesario realizar la siguiente observación:

Sean N = 5 y M = 100 
Los números de sufijo son 5, 15, 25, 35…95, lo que forma una progresión aritmética con 
primer término = 5, último término = 95, diferencia común = Base de N (por ejemplo: 6 tiene base 10, 45 tiene base 100 que no es más que la exponenciación de la forma 10 ^digitsOf(N) , donde digitsOf(N) = número de dígitos presentes en N.

Por lo tanto, para calcular el conteo de posibles números en el rango [1, M], se debe evaluar la siguiente expresión:

Número de números = Número de términos en la serie = (t _n – a)/d + 1 , donde 
t _n es el último término de la sucesión, a es el primer término de la sucesión, d es la diferencia común = (t _i+1 – t _i ), i = 1, 2, 3…n-1

A continuación se muestra la implementación del enfoque anterior:

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
 
using namespace std;
 
// Function to count the
// no. of digits of N
int digitsOf(int num)
{
    return to_string(num).size();
}
 
// Function to count all possible
// numbers having Suffix as N
int count(int a, int tn)
{
    // Difference of the A.P
    int diff = pow(10, digitsOf(a));
 
    // Count of the number of terms
    return ((tn - a) / diff) + 1;
}
 
// Driver Code
int main()
{
 
    int n, m;
    n = 25, m = 4500;
    cout << count(n, m);
 
    return 0;
}

// Java program to implement
// the above approach
import java.util.*;
 
class GFG{
 
// Function to count the
// no. of digits of N
static int digitsOf(int num)
{
    return Integer.toString(num).length();
}
 
// Function to count all possible
// numbers having Suffix as N
static int count(int a, int tn)
{
     
    // Difference of the A.P
    int diff = (int)Math.pow(10, digitsOf(a));
 
    // Count of the number of terms
    return ((tn - a) / diff) + 1;
}
 
// Driver code
public static void main (String[] args)
{
    int n = 25, m = 4500;
     
    System.out.println(count(n, m));
}
}
 
// This code is contributed by offbeat

# Python3 program to implement
# the above approach
 
# Function to count the
# no. of digits of N
def digitsOf(num):
    return len(str(num));
 
# Function to count all possible
# numbers having Suffix as N
def count(a, tn):
 
    # Difference of the A.P
    diff = int(pow(10, digitsOf(a)));
 
    # Count of the number of terms
    return ((tn - a) / diff) + 1;
 
# Driver code
if __name__ == '__main__':
    n = 25; m = 4500;
 
    print(int(count(n, m)));
 
# This code is contributed by sapnasingh4991

// C# program to implement
// the above approach
using System;
 
class GFG{
 
// Function to count the
// no. of digits of N
static int digitsOf(int num)
{
    return num.ToString().Length;
}
 
// Function to count all possible
// numbers having Suffix as N
static int count(int a, int tn)
{
     
    // Difference of the A.P
    int diff = (int)Math.Pow(10, digitsOf(a));
 
    // Count of the number of terms
    return ((tn - a) / diff) + 1;
}
 
// Driver code
public static void Main(String[] args)
{
    int n = 25, m = 4500;
     
    Console.WriteLine(count(n, m));
}
}
 
// This code is contributed by PrinciRaj1992

<script>
 
// JavaScript program to implement
// the above approach
 
// Function to count the
// no. of digits of N
function digitsOf(num)
{
    return num.toString().length;
}
  
// Function to count all possible
// numbers having Suffix as N
function count(a, tn)
{
      
    // Difference of the A.P
    let diff = Math.floor(Math.pow(10, digitsOf(a)));
  
    // Count of the number of terms
    return Math.floor((tn - a) / diff) + 1;
}
 
// Driver Code
 
    let n = 25, m = 4500;
      
    document.write(count(n, m));
            
</script>

45

Tiempo Complejidad: O(1) 
Espacio Auxiliar: O(1)