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

2021年4月15日18:51:08 发表评论 1,052 次浏览

本文概述

在从0到n的所有数字中, 将2s的数量计为数字。

例子 ：

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

输出如下：

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

改进的解决方案

想法是逐位查看问题。描绘一个数字序列：

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

我们知道, 大约有十分之一的时间, 最后一位数字将是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#

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

输出如下：

6
20

时间复杂度：O(n)

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: