Number of occurrences of 2 as a digit in numbers from 0 to n
Count the number of 2s as digit in all numbers from 0 to n.
Examples :
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 iterate through all numbers from 0 to n. For every number being visited, count the number of 2’s in it. Finally return total count.
Below is implementation of the 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 import java.io.*; 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
Time Complexity: O(n*log(n))
Auxiliary Space: O(1)
Below is an alternate implementation of this approach.
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 import java.io.*; 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
Time Complexity: O(n)
Auxiliary Space: O(no.of.digits)
Improved Solution
The idea is to look at the problem digit by digit. Picture 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 119
We know that roughly one tenth of the time, the last digit will be a 2 since it happens once in any sequence of ten numbers. In fact, any digit is a 2 roughly one tenth of the time.
We say “roughly” because there are (very common) boundary conditions. For example, between 1 and 100, the 10’s digit is a 2 exactly 1/10th of the time. However, between 1 and 37, the 10’s digit is a 2 much more than 1/10th of the time.
We can work out what exactly the ratio is by looking at the three cases individually: digit 2.
Case digits < 2
Consider the value x = 61523 and digit at index d = 3 (here indexes are considered from right and rightmost index is 0). We observe that x[d] = 1. There are 2s at the 3rd digit in the ranges 2000 – 2999, 12000 – 12999, 22000 – 22999, 32000 32999, 42000 – 42999, and 52000 – 52999. So there are 6000 2’s total in the 3rd digit. This is the same amount as if we were just counting all the 2s in the 3rd digit between 1 and 60000.
In other words, we can round down to the nearest 10d+1, and then divide by 10, to compute the number of 2s in the d-th digit.
if x[d) < 2: count2sinRangeAtDigit(x, d) = Compute y = round down to nearest 10d+1 return y/10
Case digit > 2
Now, let’s look at the case where d-th digit (from right) of x is greater than 2 (x[d] > 2). We can apply almost the exact same logic to see that there are the same number of 2s in the 3rd digit in the range 0 – 63525 as there as in the range 0 – 70000. So, rather than rounding down, we round up.
if x[d) > 2: count2sinRangeAtDigit(x, d) = Compute y = round down to nearest 10d+1 return y / 10
Case digit = 2
The final case may be the trickiest, but it follows from the earlier logic. Consider x = 62523 and d = 3. We know that there are the same ranges of 2s from before (that is, the ranges 2000 – 2999, 12000 – 12999, … , 52000 – 52999). How many appear in the 3rd digit in the final, partial range from 62000 – 62523? Well, that should be pretty easy. It’s just 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
Now, all we need is to iterate through each digit in the number. Implementing this code is reasonably straightforward.
Below is the implementation of the 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 import java.io.*; 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
Time Complexity:O(logN)
Auxiliary Space: O(1)
This article is contributed by Mr. Somesh Awasthi.