Overview of this article
In all numbers from 0 to n, count the number of 2s as digits.
example:
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);A simple brute force solution is to loop through all numbers from 0 to n. For each number visited, count 2 of them. Finally return the total.
Below is the implementation of this 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 mittalPHP
<?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.
?>The output is as follows:
6
20The following is an alternative implementation of this method in Python.
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))The output is as follows:
13Improved solution
The idea is to look at the problem bit by bit. Describe a sequence of numbers:
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 119We know that about one tenth of the time, the last digit will be 2, because it occurs once in any order of ten digits. In fact, any number is approximately one tenth of two.
We say “approximately” because there are (very common) boundary conditions. For example, between 1 and 100, the number 10 is 1/10th of the time 2. However, between 1 and 37, the number 10 is greater than 1/10th of the time.
We can determine the exact value of the ratio by looking at the following three cases separately: Number 2.
Number of cases <2
Consider the value x = 61523, the number at index d = 3 (here the indices are considered from the right, the rightmost index is 0). We observe that x[d] =1. There are 2s in the third digit of the ranges 2000 – 2999, 12000 – 12999, 22000 – 22999, 32000 32999, 42000 – 42999 and 52000 – 52999. So there are a total of 6000 2 in the third number. This is the same as if we just counted all 2’s between 1 and 60000 in the third number.
In other words, we can round to the nearest 10d + 1 and divide by 10 to calculate the 2-digit number of the dth digit.
if x[d) <2: count2sinRangeAtDigit(x, d) =
Compute y = round down to nearest 10d+1
return y/10Case Number > 2
Now, let’s look at the case where the dth number of x (from the right) is greater than 2 (x[d]>2). We can apply almost exactly the same logic to observe that a number with a third digit in the range 0 to 63525 is the same as a number with 2 digits in the range 0 to 70000. Therefore, we round instead of round.
if x[d)> 2: count2sinRangeAtDigit(x, d) =
Compute y = round down to nearest 10d+1
return y /10Number of cases = 2
The final case is probably the trickiest, but it follows the previous logic. Consider x = 62523 and d =3. We know that the same range existed from 2s to before (i.e. 2000 – 2999, 12000 – 12999, …, 52000 – 52999). In the last part of the numbers 62000 – 62523, how many are in the 3rd digit? Well, that should be easy. There are only 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 + 1Now, all we need to do is iterate through each digit in the number. Implementing this code is fairly simple.
Below is the implementation of this 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 PrinciRaj1992Python3
# 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 mitsC#
//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 mitsPHP
<?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
?>The output is as follows:
6
20Time complexity: O(n)
