Cuente el número de 2 como dígito en todos los números del 0 al n.
Ejemplos:
Input : 22
Output : 6
Explanation: Total 2s that appear as digit
from 0 to 22 are (2, 12, 20,
21, 22);
Input : 100
Output : 20
Explanation: total 2's comes between 0 to 100
are (2, 12, 20, 21, 22..29, 32, 42, 52, 62, 72,
82, 92);
Una solución de fuerza bruta simple es iterar a través de todos los números de 0 a n. Por cada número visitado, cuente el número de 2 que hay en él. Finalmente devuelva el recuento total.
A continuación se muestra la implementación de la idea.
C++
// C++ program to count 2s from 0 to n
#include <bits/stdc++.h>
using namespace std;
// Counts the number of '2'
// digits in a single number
int number0f2s(int n)
{
int count = 0;
while (n > 0)
{
if (n % 10 == 2)
count++;
n = n / 10;
}
return count;
}
// Counts the number of '2'
// digits between 0 and n
int numberOf2sinRange(int n)
{
// Initialize result
int count = 0 ;
// Count 2's in every number
// from 2 to n
for (int i = 2; i <= n; i++)
count += number0f2s(i);
return count;
}
// Driver Code
int main()
{
cout << numberOf2sinRange(22);
cout << endl;
cout << numberOf2sinRange(100);
return 0;
}
Java
// Java program to count 2s from 0 to n
class GFG
{
// Counts the number of '2'
// digits in a single number
static int number0f2s(int n)
{
int count = 0;
while (n > 0)
{
if (n % 10 == 2)
count++;
n = n / 10;
}
return count;
}
// Counts the number of '2'
// digits between 0 and n
static int numberOf2sinRange(int n)
{
// Initialize result
int count = 0;
// Count 2's in every number
// from 2 to n
for (int i = 2; i <= n; i++)
count += number0f2s(i);
return count;
}
// Driver code
public static void main(String[] args)
{
System.out.print(numberOf2sinRange(22));
System.out.println();
System.out.print(numberOf2sinRange(100));
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python3 program to count # 2s from 0 to n # Counts the number of # '2' digits in a # single number def number0f2s(n): count = 0 while (n > 0): if (n % 10 == 2): count = count + 1 n = n // 10 return count # Counts the number of '2' # digits between 0 and n def numberOf2sinRange(n): # Initialize result count = 0 # Count 2's in every number # from 2 to n for i in range(2, n + 1): count = count + number0f2s(i) return count # Driver code print(numberOf2sinRange(22)) print(numberOf2sinRange(100)) # This code is contributed # by Anant Agarwal.
C#
// C# program to count 2s from 0 to n
using System;
class GFG
{
// Counts the number of '2' digits
// in a single number
static int number0f2s(int n)
{
int count = 0;
while (n > 0)
{
if (n % 10 == 2)
count++;
n = n / 10;
}
return count;
}
// Counts the number of '2' digits
// between 0 and n
static int numberOf2sinRange(int n)
{
// Initialize result
int count = 0;
// Count 2's in every number
// from 2 to n
for (int i = 2; i <= n; i++)
count += number0f2s(i);
return count;
}
// Driver code
public static void Main()
{
Console.Write(numberOf2sinRange(22));
Console.WriteLine();
Console.Write(numberOf2sinRange(100));
}
}
// This code is contributed by nitin mittal
PHP
<?php
// php program to count 2s from 0 to n
// Counts the number of '2'
// digits in a single number
function number0f2s($n)
{
$count = 0;
while ($n > 0)
{
if ($n % 10 == 2)
$count++;
$n = $n / 10;
}
return $count;
}
// Counts the number of '2'
// digits between 0 and n
function numberOf2sinRange($n)
{
// Initialize result
$count = 0 ;
// Count 2's in every number
// from 2 to n
for ($i = 2; $i <= $n; $i++)
$count += number0f2s($i);
return $count;
}
// Driver Code
echo (numberOf2sinRange(22));
echo "\n";
echo numberOf2sinRange(100);
// This code is contributed by
// nitin mittal.
?>
Javascript
<script>
// JavaScript program to count 2s from 0 to n
// Counts the number of '2'
// digits in a single number
function number0f2s(n)
{
let count = 0;
while (n > 0)
{
if (n % 10 == 2)
count++;
n = parseInt(n / 10, 10);
}
return count;
}
// Counts the number of '2'
// digits between 0 and n
function numberOf2sinRange(n)
{
// Initialize result
let count = 0 ;
// Count 2's in every number
// from 2 to n
for (let i = 2; i <= n; i++)
count += number0f2s(i);
return count;
}
document.write(numberOf2sinRange(22) + "</br>");
document.write(numberOf2sinRange(100));
</script>
6 20
A continuación se muestra una implementación alternativa de este enfoque.
C++
// Write C++ code here
#include <bits/stdc++.h>
using namespace std;
int numberOf2sinRange(int n)
{
string s = "";
for(int i = 0; i < n + 1; i++)
s += to_string(i);
int count = 0;
for(int i = 0; i < s.length(); i++)
{
if(s[i] == '2')
{
count++;
}
}
return count;
}
// Driver code
int main()
{
int n = 30;
cout << numberOf2sinRange(n);
return 0;
}
// This code is contributed by divyeshrabadiya07.
Java
// Java code for above implementation
class GFG
{
static int numberOf2sinRange(int n)
{
String s = "";
for(int i = 0; i < n + 1; i++)
s += String.valueOf(i);
int count = 0;
for(int i = 0; i < s.length(); i++)
{
if(s.charAt(i) == '2')
{
count++;
}
}
return count;
}
// Driver code
public static void main(String[] args) {
int n = 30;
System.out.println(numberOf2sinRange(n));
}
}
// This code is contributed by divyesh072019
Python3
# Write Python3 code here
def numberOf2sinRange(n):
s = ""
for i in range(0,n+1):
s+=str(i)
return(list(s).count('2'))
# Driver code
n = 30
print(numberOf2sinRange(n))
C#
// C# code for above implementation
using System;
class GFG
{
static int numberOf2sinRange(int n)
{
string s = "";
for(int i = 0; i < n + 1; i++)
s += i + "";
int count = 0;
for(int i = 0; i < s.Length; i++)
{
if(s[i] == '2')
{
count++;
}
}
return count;
}
// Driver code
public static void Main(string[] args)
{
int n = 30;
Console.Write(numberOf2sinRange(n));
}
}
// This code is contributed by rutvik_56.
Javascript
<script>
// Javascript code for above implementation
function numberOf2sinRange(n)
{
var s = "";
for(var i = 0; i < n + 1; i++)
s += i.toString();
var count = 0;
for(var i = 0; i < s.length; i++)
{
if (s.charAt(i) == '2')
{
count++;
}
}
return count;
}
// Driver code
var n = 30;
document.write(numberOf2sinRange(n));
// This code is contributed by Princi Singh
</script>
13
Solución mejorada
La idea es mirar el problema dígito por dígito. Imagina una secuencia de números:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 ...... 110 111 112 113 114 115 116 117 118 119
Sabemos que aproximadamente una décima parte de las veces, el último dígito será un 2, ya que ocurre una vez en cualquier secuencia de diez números. De hecho, cualquier dígito es un 2 aproximadamente una décima parte del tiempo.
Decimos «aproximadamente» porque existen condiciones de contorno (muy comunes). Por ejemplo, entre 1 y 100, el dígito de las 10 es un 2 exactamente 1/10 del tiempo. Sin embargo, entre 1 y 37, el dígito de los 10 es un 2 mucho más que 1/10 del tiempo.
Podemos averiguar cuál es exactamente la razón mirando los tres casos individualmente: dígito 2.
Caso de dígitos < 2
Considere el valor x = 61523 y el dígito en el índice d = 3 (aquí los índices se consideran desde la derecha y el índice más a la derecha es 0). Observamos que x[d] = 1. Hay 2 en el tercer dígito en los rangos 2000 – 2999, 12000 – 12999, 22000 – 22999, 32000 32999, 42000 – 42999 y 52000 – 52999. Así que hay 6000 2 en total en el 3er dígito. Esta es la misma cantidad que si estuviéramos contando todos los 2 en el tercer dígito entre 1 y 60000.
En otras palabras, podemos redondear hacia abajo al 10 d+1 más cercano y luego dividir por 10 para calcular el número de 2 en el d-ésimo dígito.
if x[d) < 2: count2sinRangeAtDigit(x, d) = Compute y = round down to nearest 10d+1 return y/10
Caso dígito > 2
Ahora, veamos el caso donde el d-ésimo dígito (desde la derecha) de x es mayor que 2 (x[d] > 2). Podemos aplicar casi exactamente la misma lógica para ver que hay la misma cantidad de 2 en el tercer dígito en el rango de 0 a 63525 que en el rango de 0 a 70000. Entonces, en lugar de redondear hacia abajo, redondeamos hacia arriba.
if x[d) > 2: count2sinRangeAtDigit(x, d) = Compute y = round down to nearest 10d+1 return y / 10
Caso dígito = 2
El caso final puede ser el más complicado, pero se deriva de la lógica anterior. Considere x = 62523 y d = 3. Sabemos que hay los mismos rangos de 2s de antes (es decir, los rangos 2000 – 2999, 12000 – 12999, … , 52000 – 52999). ¿Cuántos aparecen en el tercer dígito en el rango parcial final de 62000 a 62523? Bueno, eso debería ser bastante fácil. Es solo 524 (62000, 62001, …, 62523).
if x[d] = 2: count2sinRangeAtDigit(x, d) = Compute y = round down to nearest 10d+1 Compute z = right side of x (i.e., x% 10d) return y/10 + z + 1
Ahora, todo lo que necesitamos es iterar a través de cada dígito en el número. La implementación de este código es razonablemente sencilla.
A continuación se muestra la implementación de la idea.
C++
// C++ program to count 2s from 0 to n
#include <bits/stdc++.h>
using namespace std;
// Counts the number of 2s
// in a number at d-th digit
int count2sinRangeAtDigit(int number, int d)
{
int powerOf10 = (int)pow(10, d);
int nextPowerOf10 = powerOf10 * 10;
int right = number % powerOf10;
int roundDown = number - number % nextPowerOf10;
int roundup = roundDown + nextPowerOf10;
int digit = (number / powerOf10) % 10;
// if the digit in spot digit is
if (digit < 2)
return roundDown / 10;
if (digit == 2)
return roundDown / 10 + right + 1;
return roundup / 10;
}
// Counts the number of '2' digits between 0 and n
int numberOf2sinRange(int number)
{
// Convert integer to String
// to find its length
stringstream convert;
convert << number;
string s = convert.str();
int len = s.length();
// Traverse every digit and
// count for every digit
int count = 0;
for (int digit = 0; digit < len; digit++)
count += count2sinRangeAtDigit(number, digit);
return count;
}
// Driver Code
int main()
{
cout << numberOf2sinRange(22) << endl;
cout << numberOf2sinRange(100);
return 0;
}
Java
// Java program to count 2s from 0 to n
class GFG
{
// Counts the number of 2s
// in a number at d-th digit
static int count2sinRangeAtDigit(int number, int d)
{
int powerOf10 = (int) Math.pow(10, d);
int nextPowerOf10 = powerOf10 * 10;
int right = number % powerOf10;
int roundDown = number - number % nextPowerOf10;
int roundup = roundDown + nextPowerOf10;
int digit = (number / powerOf10) % 10;
// if the digit in spot digit is
if (digit < 2)
{
return roundDown / 10;
}
if (digit == 2)
{
return roundDown / 10 + right + 1;
}
return roundup / 10;
}
// Counts the number of '2' digits between 0 and n
static int numberOf2sinRange(int number)
{
// Convert integer to String
// to find its length
String convert;
convert = String.valueOf(number);
String s = convert;
int len = s.length();
// Traverse every digit and
// count for every digit
int count = 0;
for (int digit = 0; digit < len; digit++)
{
count += count2sinRangeAtDigit(number, digit);
}
return count;
}
// Driver Code
public static void main(String[] args)
{
System.out.println(numberOf2sinRange(22));
System.out.println(numberOf2sinRange(100));
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 program to count 2s from 0 to n # Counts the number of 2s in a # number at d-th digit def count2sinRangeAtDigit(number, d): powerOf10 = int(pow(10, d)); nextPowerOf10 = powerOf10 * 10; right = number % powerOf10; roundDown = number - number % nextPowerOf10; roundup = roundDown + nextPowerOf10; digit = (number // powerOf10) % 10; # if the digit in spot digit is if (digit < 2): return roundDown // 10; if (digit == 2): return roundDown // 10 + right + 1; return roundup // 10; # Counts the number of '2' digits # between 0 and n def numberOf2sinRange(number): # Convert integer to String # to find its length s = str(number); len1 = len(s); # Traverse every digit and # count for every digit count = 0; for digit in range(len1): count += count2sinRangeAtDigit(number, digit); return count; # Driver Code print(numberOf2sinRange(22)); print(numberOf2sinRange(100)); # This code is contributed by mits
C#
// C# program to count 2s from 0 to n
using System;
class GFG
{
// Counts the number of 2s
// in a number at d-th digit
static int count2sinRangeAtDigit(int number,
int d)
{
int powerOf10 = (int) Math.Pow(10, d);
int nextPowerOf10 = powerOf10 * 10;
int right = number % powerOf10;
int roundDown = number - number % nextPowerOf10;
int roundup = roundDown + nextPowerOf10;
int digit = (number / powerOf10) % 10;
// if the digit in spot digit is
if (digit < 2)
{
return roundDown / 10;
}
if (digit == 2)
{
return roundDown / 10 + right + 1;
}
return roundup / 10;
}
// Counts the number of '2' digits
// between 0 and n
static int numberOf2sinRange(int number)
{
// Convert integer to String
// to find its length
string convert;
convert = number.ToString();
string s = convert;
int len = s.Length;
// Traverse every digit and
// count for every digit
int count = 0;
for (int digit = 0; digit < len; digit++)
{
count += count2sinRangeAtDigit(number,
digit);
}
return count;
}
// Driver Code
public static void Main()
{
Console.WriteLine(numberOf2sinRange(22));
Console.WriteLine(numberOf2sinRange(100));
}
}
// This code is contributed by mits
PHP
<?php
// PHP program to count 2s from 0 to n
// Counts the number of 2s in a number
// at d-th digit
function count2sinRangeAtDigit($number, $d)
{
$powerOf10 = (int)pow(10, $d);
$nextPowerOf10 = $powerOf10 * 10;
$right = $number % $powerOf10;
$roundDown = $number - $number %
$nextPowerOf10;
$roundup = $roundDown + $nextPowerOf10;
$digit = ($number / $powerOf10) % 10;
// if the digit in spot digit is
if ($digit < 2)
return $roundDown / 10;
if ($digit == 2)
return $roundDown / 10 + $right + 1;
return $roundup / 10;
}
// Counts the number of '2' digits
// between 0 and n
function numberOf2sinRange($number)
{
// Convert integer to String
// to find its length
$s = strval($number);
$len = strlen($s);
// Traverse every digit and
// count for every digit
$count = 0;
for ($digit = 0; $digit < $len; $digit++)
$count += count2sinRangeAtDigit($number,
$digit);
return $count;
}
// Driver Code
print(numberOf2sinRange(22) . "\n");
print(numberOf2sinRange(100) . "\n");
// This code is contributed by mits
?>
Javascript
<script>
// javascript program to count 2s from 0 to n
// Counts the number of 2s
// in a number at d-th digit
function count2sinRangeAtDigit(number , d)
{
var powerOf10 = parseInt( Math.pow(10, d));
var nextPowerOf10 = powerOf10 * 10;
var right = number % powerOf10;
var roundDown = number - number % nextPowerOf10;
var roundup = roundDown + nextPowerOf10;
var digit = parseInt(number / powerOf10) % 10;
// if the digit in spot digit is
if (digit < 2)
{
return roundDown / 10;
}
if (digit == 2)
{
return roundDown / 10 + right + 1;
}
return roundup / 10;
}
// Counts the number of '2' digits between 0 and n
function numberOf2sinRange(number)
{
// Convert integer to String
// to find its length
var convert;
convert = number.toString();
var s = convert;
var len = s.length;
// Traverse every digit and
// count for every digit
var count = 0;
for (digit = 0; digit < len; digit++)
{
count += count2sinRangeAtDigit(number, digit);
}
return count;
}
// Driver Code
document.write(numberOf2sinRange(22));
document.write("<br>"+numberOf2sinRange(100));
// This code is contributed by 29AjayKumar
</script>
6 20
Complejidad de tiempo: O (logN)
Este artículo es una contribución del Sr. Somesh Awasthi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@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