算法设计:计算d位数的正整数,以0作为数字

2021年4月10日12:56:27 发表评论 782 次浏览

本文概述

给定一个数字d, 代表正整数的位数。求出其中至少有一个零的正整数(精确地由d个数字组成)的总数。

例子:

Input : d = 1
Output : 0
There's no natural number of 1 digit that
contains a zero.

Input : d = 2
Output : 9
The numbers are, 10, 20, 30, 40, 50, 60, 70, 80 and 90.

一种简单的解决方案是遍历所有d位正数。对于每个数字, 请遍历其数字;如果有任何0数字, 则递增计数(类似于这个)。

以下是一些观察结果:

  1. 恰好有d位数字。
  2. 最高有效位的数字不能为零(不允许前导零)。
  3. 除最高有效位以外的所有其他位置可以包含零。
数字

因此, 考虑以上几点, 让我们找到具有d位数字的总数:

We can place any of {1, 2, ... 9} in D1
Hence D1 can be filled in 9 ways.

Apart from D1 all the other places can be  10 ways. 
(we can place 0 as well)
Hence the total numbers having d digits can be given as: 
Total =  9*10d-1

Now, let's find the numbers having d digits, that
don't contain zero at any place. 
In this case, all the places can be filled in 9 ways.
Hence count of such numbers is given by:
Non_Zero = 9d

Now the count of numbers having at least one zero 
can be obtained by subtracting Non_Zero from Total.
Hence Answer would be given by:
9*(10d-1 - 9d-1 )

以下是相同的程序。

C ++

//C++ program to find the count of positive integer of a
//given number of digits that contain atleast one zero
#include<bits/stdc++.h>
using namespace std;
  
//Returns count of 'd' digit integers have 0 as a digit
int findCount( int d)
{
     return 9*( pow (10, d-1) - pow (9, d-1));
}
  
//Driver Code
int main()
{
     int d = 1;
     cout <<findCount(d) <<endl;
  
     d = 2;
     cout <<findCount(d) <<endl;
  
     d = 4;
     cout <<findCount(d) <<endl;
     return 0;
}

Java

//Java program to find the count
//of positive integer of a
//given number of digits 
//that contain atleast one zero
import java.io.*;
  
class GFG {
      
     //Returns count of 'd' digit 
     //integers have 0 as a digit
     static int findCount( int d)
     {
         return 9 * (( int )(Math.pow( 10 , d - 1 )) 
                  - ( int )(Math.pow( 9 , d - 1 )));
     }
      
     //Driver Code
     public static void main(String args[])
     {
         int d = 1 ;
         System.out.println(findCount(d));
          
         d = 2 ;
         System.out.println(findCount(d));
          
         d = 4 ;
         System.out.println(findCount(d));
          
     }
}
  
//This code is contributed by Nikita Tiwari.

Python3

# Python 3 program to find the
# count of positive integer of a
# given number of digits that
# contain atleast one zero
import math
  
# Returns count of 'd' digit
# integers have 0 as a digit
def findCount(d) :
     return 9 * (( int )(math. pow ( 10 , d - 1 )) - ( int )(math. pow ( 9 , d - 1 )));
  
  
# Driver Code
d = 1
print (findCount(d))
      
d = 2
print (findCount(d))
  
d = 4
print (findCount(d))
  
  
# This code is contributed by Nikita Tiwari.

C#

//C# program to find the count
//of positive integer of a
//given number of digits 
//that contain atleast one zero.
using System;
  
class GFG {
      
     //Returns count of 'd' digit 
     //integers have 0 as a digit
     static int findCount( int d)
     {
         return 9 * (( int )(Math.Pow(10, d - 1)) 
                  - ( int )(Math.Pow(9, d - 1)));
     }
      
     //Driver Code
     public static void Main()
     {
         int d = 1;
         Console.WriteLine(findCount(d));
          
         d = 2;
         Console.WriteLine(findCount(d));
          
         d = 4;
         Console.WriteLine(findCount(d));
          
     }
}
  
//This code is contributed by nitin mittal.

的PHP

<?php
//PHP program to find the count
//of positive integer of a given 
//number of digits that contain
//atleast one zero
  
//Returns count of 'd' digit 
//integers have 0 as a digit
function findCount( $d )
{
     return 9 * (pow(10, $d - 1) - 
                 pow(9, $d - 1));
}
  
//Driver Code
{
     $d = 1;
     echo findCount( $d ), "\n" ;
  
     $d = 2;
     echo findCount( $d ), "\n" ;
  
     $d = 4;
     echo findCount( $d ), "\n" ;
     return 0;
}
  
//This code is contributed by nitin mittal
?>

输出:

0
9
2439

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

木子山

发表评论

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