Problema: Cuente cuántos enteros del 1 al N contienen 0 como dígito.
Ejemplos:
Input: n = 9 Output: 0 Input: n = 107 Output: 17 The numbers having 0 are 10, 20,..90, 100, 101..107 Input: n = 155 Output: 24 The numbers having 0 are 10, 20,..90, 100, 101..110, 120, ..150.
En una publicación anterior se analiza una solución ingenua.
En esta publicación se analiza una solución optimizada. Analicemos el problema de cerca.
Deje que el número dado tenga d dígitos.
La respuesta requerida se puede calcular calculando los siguientes dos valores:
- Recuento de enteros de 0 dígitos con un máximo de d-1 dígitos.
- Recuento de enteros de 0 dígitos que tienen exactamente d dígitos (¡menos que/igual al número dado, por supuesto!)
Por lo tanto, la solución sería la suma de los dos anteriores.
La primera parte ya ha sido discutida aquí .
¿Cómo encontrar la segunda parte?
Podemos encontrar el número total de números enteros que tienen d dígitos (menor que igual al número dado), que no contienen ningún cero.
Para encontrar esto, recorremos el número, un dígito a la vez.
Encontramos el recuento de enteros no negativos de la siguiente manera:
- Si el número en ese lugar es cero, disminuya el contador en 1 y rompa (porque no podemos avanzar más, disminuya para asegurarse de que el número en sí contenga un cero)
- de lo contrario, multiplique el (número-1), con potencia (9, número de dígitos a la derecha)
Ilustremos con un ejemplo.
Let the number be n = 123. non_zero = 0 We encounter 1 first, add (1-1)*92 to non_zero (= 0+0) We encounter 2, add (2-1)*91 to non_zero (= 0+9 = 9) We encounter 3, add (3-1)*90 to non_zero (=9+3 = 12)
Podemos observar que non_zero denota el número de enteros que consta de 3 dígitos (no mayor que 123) y no contiene ningún cero. es decir, (111, 112, ….., 119, 121, 122, 123) (Se recomienda verificarlo una vez)
Ahora, cabe preguntarse ¿de qué sirve calcular la cuenta de números que no tienen ceros?
¡Correcto! estamos interesados en encontrar el conteo de enteros que tienen cero.
Sin embargo, ahora podemos encontrarlo fácilmente restando distinto de cero de n después de ignorar el lugar más significativo. Es decir, en nuestro ejemplo anterior cero = 23 – distinto de cero = 23-12 = 11 y finalmente sumamos las dos partes para llegar al resultado requerido !!
A continuación se muestra la implementación de la idea anterior.
C++
//Modified C++ program to count number from 1 to n with
// 0 as a digit.
#include <bits/stdc++.h>
using namespace std;
// Returns count of integers having zero upto given digits
int zeroUpto(int digits)
{
// Refer below article for details
// https://www.geeksforgeeks.org/count-positive-integers-0-digit/
int first = (pow(10,digits)-1)/9;
int second = (pow(9,digits)-1)/8;
return 9 * (first - second);
}
// utility function to convert character representation
// to integer
int toInt(char c)
{
return int(c)-48;
}
// counts numbers having zero as digits upto a given
// number 'num'
int countZero(string num)
{
// k denoted the number of digits in the number
int k = num.length();
// Calculating the total number having zeros,
// which upto k-1 digits
int total = zeroUpto(k-1);
// Now let us calculate the numbers which don't have
// any zeros. In that k digits upto the given number
int non_zero = 0;
for (int i=0; i<num.length(); i++)
{
// If the number itself contains a zero then
// decrement the counter
if (num[i] == '0')
{
non_zero--;
break;
}
// Adding the number of non zero numbers that
// can be formed
non_zero += (toInt(num[i])-1) * (pow(9,k-1-i));
}
int no = 0, remaining = 0,calculatedUpto=0;
// Calculate the number and the remaining after
// ignoring the most significant digit
for (int i=0; i<num.length(); i++)
{
no = no*10 + (toInt(num[i]));
if (i != 0)
calculatedUpto = calculatedUpto*10 + 9;
}
remaining = no-calculatedUpto;
// Final answer is calculated
// It is calculated by subtracting 9....9 (d-1) times
// from no.
int ans = zeroUpto(k-1) + (remaining-non_zero-1);
return ans;
}
// Driver program to test the above functions
int main()
{
string num = "107";
cout << "Count of numbers from 1" << " to "
<< num << " is " << countZero(num) << endl;
num = "1264";
cout << "Count of numbers from 1" << " to "
<< num << " is " <<countZero(num) << endl;
return 0;
}
Java
//Modified Java program to count number from 1 to n with
// 0 as a digit.
public class GFG {
// Returns count of integers having zero upto given digits
static int zeroUpto(int digits)
{
// Refer below article for details
// https://www.geeksforgeeks.org/count-positive-integers-0-digit/
int first = (int) ((Math.pow(10,digits)-1)/9);
int second = (int) ((Math.pow(9,digits)-1)/8);
return 9 * (first - second);
}
// utility function to convert character representation
// to integer
static int toInt(char c)
{
return (int)(c)-48;
}
// counts numbers having zero as digits upto a given
// number 'num'
static int countZero(String num)
{
// k denoted the number of digits in the number
int k = num.length();
// Calculating the total number having zeros,
// which upto k-1 digits
int total = zeroUpto(k-1);
// Now let us calculate the numbers which don't have
// any zeros. In that k digits upto the given number
int non_zero = 0;
for (int i=0; i<num.length(); i++)
{
// If the number itself contains a zero then
// decrement the counter
if (num.charAt(i) == '0')
{
non_zero--;
break;
}
// Adding the number of non zero numbers that
// can be formed
non_zero += (toInt(num.charAt(i))-1) * (Math.pow(9,k-1-i));
}
int no = 0, remaining = 0,calculatedUpto=0;
// Calculate the number and the remaining after
// ignoring the most significant digit
for (int i=0; i<num.length(); i++)
{
no = no*10 + (toInt(num.charAt(i)));
if (i != 0)
calculatedUpto = calculatedUpto*10 + 9;
}
remaining = no-calculatedUpto;
// Final answer is calculated
// It is calculated by subtracting 9....9 (d-1) times
// from no.
int ans = zeroUpto(k-1) + (remaining-non_zero-1);
return ans;
}
// Driver program to test the above functions
static public void main(String[] args) {
String num = "107";
System.out.println("Count of numbers from 1" + " to "
+ num + " is " + countZero(num));
num = "1264";
System.out.println("Count of numbers from 1" + " to "
+ num + " is " +countZero(num));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to count number from 1 to n
# with 0 as a digit.
# Returns count of integers having zero
# upto given digits
def zeroUpto(digits):
first = int((pow(10, digits) - 1) / 9);
second = int((pow(9, digits) - 1) / 8);
return 9 * (first - second);
# counts numbers having zero as digits
# upto a given number 'num'
def countZero(num):
# k denoted the number of digits
# in the number
k = len(num);
# Calculating the total number having
# zeros, which upto k-1 digits
total = zeroUpto(k - 1);
# Now let us calculate the numbers which
# don't have any zeros. In that k digits
# upto the given number
non_zero = 0;
for i in range(len(num)):
# If the number itself contains a zero
# then decrement the counter
if (num[i] == '0'):
non_zero -= 1;
break;
# Adding the number of non zero numbers
# that can be formed
non_zero += (((ord(num[i]) - ord('0')) - 1) *
(pow(9, k - 1 - i)));
no = 0;
remaining = 0;
calculatedUpto = 0;
# Calculate the number and the remaining
# after ignoring the most significant digit
for i in range(len(num)):
no = no * 10 + (ord(num[i]) - ord('0'));
if (i != 0):
calculatedUpto = calculatedUpto * 10 + 9;
remaining = no - calculatedUpto;
# Final answer is calculated. It is calculated
# by subtracting 9....9 (d-1) times from no.
ans = zeroUpto(k - 1) + (remaining - non_zero - 1);
return ans;
# Driver Code
num = "107";
print("Count of numbers from 1 to",
num, "is", countZero(num));
num = "1264";
print("Count of numbers from 1 to",
num, "is", countZero(num));
# This code is contributed by mits
C#
// Modified C# program to count number from 1 to n with
// 0 as a digit.
using System;
public class GFG{
// Returns count of integers having zero upto given digits
static int zeroUpto(int digits)
{
// Refer below article for details
// https://www.geeksforgeeks.org/count-positive-integers-0-digit/
int first = (int) ((Math.Pow(10,digits)-1)/9);
int second = (int) ((Math.Pow(9,digits)-1)/8);
return 9 * (first - second);
}
// utility function to convert character representation
// to integer
static int toInt(char c)
{
return (int)(c)-48;
}
// counts numbers having zero as digits upto a given
// number 'num'
static int countZero(String num)
{
// k denoted the number of digits in the number
int k = num.Length;
// Calculating the total number having zeros,
// which upto k-1 digits
int total = zeroUpto(k-1);
// Now let us calculate the numbers which don't have
// any zeros. In that k digits upto the given number
int non_zero = 0;
for (int i=0; i<num.Length; i++)
{
// If the number itself contains a zero then
// decrement the counter
if (num[i] == '0')
{
non_zero--;
break;
}
// Adding the number of non zero numbers that
// can be formed
non_zero += (toInt(num[i])-1) * (int)(Math.Pow(9,k-1-i));
}
int no = 0, remaining = 0,calculatedUpto=0;
// Calculate the number and the remaining after
// ignoring the most significant digit
for (int i=0; i<num.Length; i++)
{
no = no*10 + (toInt(num[i]));
if (i != 0)
calculatedUpto = calculatedUpto*10 + 9;
}
remaining = no-calculatedUpto;
// Final answer is calculated
// It is calculated by subtracting 9....9 (d-1) times
// from no.
int ans = zeroUpto(k-1) + (remaining-non_zero-1);
return ans;
}
// Driver program to test the above functions
static public void Main() {
String num = "107";
Console.WriteLine("Count of numbers from 1" + " to "
+ num + " is " + countZero(num));
num = "1264";
Console.WriteLine("Count of numbers from 1" + " to "
+ num + " is " +countZero(num));
}
}
// This code is contributed by 29AjayKumar
PHP
<?php
// PHP program to count
// number from 1 to n
// with 0 as a digit.
// Returns count of integers
// having zero upto given digits
function zeroUpto($digits)
{
$first = (int)((pow(10,
$digits) - 1) / 9);
$second = (int)((pow(9,
$digits) - 1) / 8);
return 9 * ($first - $second);
}
// counts numbers having
// zero as digits upto a
// given number 'num'
function countZero($num)
{
// k denoted the number
// of digits in the number
$k = strlen($num);
// Calculating the total
// number having zeros,
// which upto k-1 digits
$total = zeroUpto($k-1);
// Now let us calculate
// the numbers which don't
// have any zeros. In that
// k digits upto the given
// number
$non_zero = 0;
for ($i = 0;
$i < strlen($num); $i++)
{
// If the number itself
// contains a zero then
// decrement the counter
if ($num[$i] == '0')
{
$non_zero--;
break;
}
// Adding the number of
// non zero numbers that
// can be formed
$non_zero += (($num[$i] - '0') - 1) *
(pow(9, $k - 1 - $i));
}
$no = 0;
$remaining = 0;
$calculatedUpto = 0;
// Calculate the number
// and the remaining after
// ignoring the most
// significant digit
for ($i = 0;
$i < strlen($num); $i++)
{
$no = $no * 10 + ($num[$i] - '0');
if ($i != 0)
$calculatedUpto = $calculatedUpto *
10 + 9;
}
$remaining = $no - $calculatedUpto;
// Final answer is calculated
// It is calculated by subtracting
// 9....9 (d-1) times from no.
$ans = zeroUpto($k - 1) +
($remaining -
$non_zero - 1);
return $ans;
}
// Driver Code
$num = "107";
echo "Count of numbers from 1 to " .
$num . " is " .
countZero($num) . "\n";
$num = "1264";
echo "Count of numbers from 1 to " .
$num . " is " .
countZero($num);
// This code is contributed
// by mits
?>
Javascript
<script>
// Modified javascript program to count number from 1 to n with
// 0 as a digit.
// Returns count of integers having zero upto given digits
function zeroUpto(digits)
{
// Refer below article for details
// https://www.geeksforgeeks.org/count-positive-integers-0-digit/
var first = parseInt( ((Math.pow(10,digits)-1)/9));
var second = parseInt( ((Math.pow(9,digits)-1)/8));
return 9 * (first - second);
}
// utility function to convert character representation
// to integer
function toInt(c)
{
return parseInt((c.charCodeAt(0))-48);
}
// counts numbers having zero as digits upto a given
// number 'num'
function countZero(num)
{
// k denoted the number of digits in the number
var k = num.length;
// Calculating the total number having zeros,
// which upto k-1 digits
var total = zeroUpto(k-1);
// Now let us calculate the numbers which don't have
// any zeros. In that k digits upto the given number
var non_zero = 0;
for (i=0; i<num.length; i++)
{
// If the number itself contains a zero then
// decrement the counter
if (num.charAt(i) == '0')
{
non_zero--;
break;
}
// Adding the number of non zero numbers that
// can be formed
non_zero += (toInt(num.charAt(i))-1) * (Math.pow(9,k-1-i));
}
var no = 0, remaining = 0,calculatedUpto=0;
// Calculate the number and the remaining after
// ignoring the most significant digit
for (i=0; i<num.length; i++)
{
no = no*10 + (toInt(num.charAt(i)));
if (i != 0)
calculatedUpto = calculatedUpto*10 + 9;
}
remaining = no-calculatedUpto;
// Final answer is calculated
// It is calculated by subtracting 9....9 (d-1) times
// from no.
var ans = zeroUpto(k-1) + (remaining-non_zero-1);
return ans;
}
// Driver program to test the above functions
var num = "107";
document.write("Count of numbers from 1" + " to "
+ num + " is " + countZero(num));
var num = "1264";
document.write("<br>Count of numbers from 1" + " to "
+ num + " is " +countZero(num));
// This code is contributed by shikhasingrajput
</script>
Producción:
Count of numbers from 1 to 107 is 17 Count of numbers from 1 to 1264 is 315
Análisis de
Complejidad: Complejidad de Tiempo: O(d), donde d es no. de dígitos, es decir, O(log(n)
Espacio auxiliar: O(1)
Este artículo es una contribución de Ashutosh Kumar . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo electrónico a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA