算法题（2的出现次数（从0到n的数字）） _从0到n的数字

本文概述

C++
Java
Python3
C#
PHP
Python3
C++
Java
Python3
C#
PHP

在从0到n的所有数字中, 将2s的数量计为数字。
【算法题（2的出现次数（从0到n的数字））】例子：

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);

一种简单蛮力解决方案是遍历从0到n的所有数字。对于访问的每个数字, 请计算其中的2。最后返回总数。
以下是该想法的实现。
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 nclass 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 + 1n = n //10return 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 codeprint (numberOf2sinRange( 22 )) print (numberOf2sinRange( 100 ))# This code is contributed # by Anant Agarwal.

//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. ?>

输出如下：

6 20

以下是此方法在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))

输出如下：

13

改进的解决方案
想法是逐位查看问题。描绘一个数字序列：

0123456789 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

我们知道, 大约有十分之一的时间, 最后一位数字将是2, 因为它以十个数字的任何顺序出现一次。实际上, 任何数字大约是十分之一的2。
我们说"大致"是因为存在(非常常见的)边界条件。例如, 在1到100之间, 10的数字就是2的1/10th的时间。但是, 在1到37之间, 10的数字比1/10大2th的时间。
我们可以通过分别查看以下三种情况来确定比率的确切值：数字2。
个案数字< 2
考虑值x = 61523, 索引d = 3处的数字(此处从右边开始考虑索引, 最右边的索引为0)。我们观察到x [d] =1。在2000 – 2999、12000 – 12999、22000 – 22999、32000 32999、42000 – 42999和52000 – 52999范围的第三位有2s。所以总共有6000 2在第三个数字。这与我们只计算第三个数字中所有1到60000之间的2相同。
换句话说, 我们可以四舍五入到最接近的10d + 1, 然后除以10, 以计算第d位数字的2位数。

if x[d) < 2: count2sinRangeAtDigit(x, d) = Compute y = round down to nearest 10d+1 return y/10

案例数字> 2
现在, 让我们看一下x的第d个数字(从右开始)大于2(x [d]> 2)的情况。我们可以应用几乎完全相同的逻辑来观察, 第三位数在0到63525范围内的数字与2位数在0到70000范围内是相同的。因此, 我们舍入而不是舍入。

if x[d)> 2: count2sinRangeAtDigit(x, d) = Compute y = round down to nearest 10d+1 return y /10

案例数= 2
最终的情况可能是最棘手的, 但它遵循先前的逻辑。考虑x = 62523和d =3。我们知道从2s到之前存在相同的范围(即2000 – 2999、12000 – 12999, …, 52000 – 52999)。在最后的部分数字62000 – 62523中, 第3位有多少个？好吧, 那应该很容易。只有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

现在, 我们所需要做的就是遍历数字中的每个数字。实施此代码相当简单。
以下是该想法的实现。
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# 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 ?>

输出如下：