Dado un rango de L a R y un entero K , la tarea es contar el número de enteros en el rango dado de manera que sus últimos K dígitos sean iguales.
Ejemplo:
Entrada: L = 49, R = 101, K=2
Salida: 6
Explicación: Hay 6 enteros posibles te, 55, 66, 77, 88, 99 y 100 tales que sus últimos K (es decir, 2) dígitos son iguales.Entrada: L = 10, R = 20, K=2
Salida: 1
Enfoque eficiente: se puede observar que el conteo de números enteros i en el rango de 1 a X que tienen los últimos K dígitos iguales a un número entero z (es decir, i % 10 K = z) son (X – z)/10 K + 1 . Usando esta observación, el problema anterior se puede resolver usando los siguientes pasos:
- Supongamos que intCount(X, K) representa el recuento de números enteros del 1 al X que tienen los últimos K dígitos como iguales.
- Para calcular intCount(X, K) , itere sobre todas las posibilidades de que z tenga K dígitos (es decir, {00…0, 11…1, 22…2, 33…3, 44…4, …., 99…9 } ) en la fórmula (X – z)/10 K +1 y mantener su suma que es el valor requerido.
- Por lo tanto, el conteo de enteros en el rango L a R se puede obtener como intCount(R, K) – intCount(L-1, K) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the count of
// integers from 1 to X having the
// last K digits as equal
int intCount(int X, int K)
{
// Stores the total count of integers
int ans = 0;
// Loop to iterate over all
// possible values of z
for (int z = 0; z < pow(10, K);
z += (pow(10, K) - 1) / 9) {
// Terminate the loop when z > X
if (z > X)
break;
// Add count of integers with
// last K digits equal to z
ans += ((X - z) / pow(10, K) + 1);
}
// Return count
return ans;
}
// Function to return the count of
// integers from L to R having the
// last K digits as equal
int intCountInRange(int L, int R, int K)
{
return (intCount(R, K)
- intCount(L - 1, K));
}
// Driver Code
int main()
{
int L = 49;
int R = 101;
int K = 2;
// Function Call
cout << intCountInRange(L, R, K);
return 0;
}
Java
// Java Program of the above approach
import java.util.*;
class GFG{
// Function to return the count of
// integers from 1 to X having the
// last K digits as equal
static int intCount(int X, int K)
{
// Stores the total count of integers
int ans = 0;
// Loop to iterate over all
// possible values of z
for (int z = 0; z < Math.pow(10, K);
z += (Math.pow(10, K) - 1) / 9) {
// Terminate the loop when z > X
if (z > X)
break;
// Add count of integers with
// last K digits equal to z
ans += ((X - z) / Math.pow(10, K) + 1);
}
// Return count
return ans;
}
// Function to return the count of
// integers from L to R having the
// last K digits as equal
static int intCountInRange(int L, int R, int K)
{
return (intCount(R, K)
- intCount(L - 1, K));
}
// Driver Code
public static void main(String[] args)
{
int L = 49;
int R = 101;
int K = 2;
// Function Call
System.out.print(intCountInRange(L, R, K));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach # Function to return the count of # integers from 1 to X having the # last K digits as equal def intCount(X, K): # Stores the total count of integers ans = 0 # Loop to iterate over all # possible values of z for z in range(0, int(pow(10, K)), int((pow(10, K) - 1) / 9)): # Terminate the loop when z > X if (z > X): break # Add count of integers with # last K digits equal to z ans += int((X - z) / int(pow(10, K)) + 1) # Return count return ans # Function to return the count of # integers from L to R having the # last K digits as equal def intCountInRange(L, R, K): return(intCount(R, K) - intCount(L - 1, K)) # Driver Code L = 49 R = 101 K = 2 # Function Call print(intCountInRange(L, R, K)) # This code is contributed by sanjoy_62
C#
// C# Program of the above approach
using System;
class GFG{
// Function to return the count of
// integers from 1 to X having the
// last K digits as equal
static int intCount(int X, int K)
{
// Stores the total count of integers
int ans = 0;
// Loop to iterate over all
// possible values of z
for (int z = 0; z < Math.Pow(10, K);
z += ((int)Math.Pow(10, K) - 1) / 9) {
// Terminate the loop when z > X
if (z > X)
break;
// Add count of integers with
// last K digits equal to z
ans += ((X - z) / (int)Math.Pow(10, K) + 1);
}
// Return count
return ans;
}
// Function to return the count of
// integers from L to R having the
// last K digits as equal
static int intCountInRange(int L, int R, int K)
{
return (intCount(R, K)
- intCount(L - 1, K));
}
// Driver Code
public static void Main(String[] args)
{
int L = 49;
int R = 101;
int K = 2;
// Function Call
Console.Write(intCountInRange(L, R, K));
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
// JavaScript program for the above approach
// Function to return the count of
// integers from 1 to X having the
// last K digits as equal
function intCount(X, K)
{
// Stores the total count of integers
let ans = 0;
// Loop to iterate over all
// possible values of z
for(let z = 0; z < Math.pow(10, K);
z += Math.floor((Math.pow(10, K) - 1) / 9))
{
// Terminate the loop when z > X
if (z > X)
break;
// Add count of integers with
// last K digits equal to z
ans += Math.floor(((X - z) /
Math.pow(10, K) + 1));
}
// Return count
return ans;
}
// Function to return the count of
// integers from L to R having the
// last K digits as equal
function intCountInRange(L, R, K)
{
return(intCount(R, K) -
intCount(L - 1, K));
}
// Driver Code
let L = 49;
let R = 101;
let K = 2;
// Function Call
document.write(intCountInRange(L, R, K));
// This code is contributed by Potta Lokesh
</script>
Producción
6
Complejidad de tiempo: O(log K)
Complejidad de espacio: O(1)
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA