Count n digit numbers not having a particular digit
We are given two integers n and d, we need to count all n digit numbers that do not have digit d.
Example :
Input : n = 2, d = 7 Output : 72 All two digit numbers that don't have 7 as digit are 10, 11, 12, 13, 14, 15, 16, 18, ..... Input : n = 3, d = 9 Output : 648
A simple solution is to traverse through all d digit numbers. For every number, check if it has x as digit or not.
Efficient approach In this method, we check first if excluding digit d is zero or non-zero. If it is zero then, we have 9 numbers (1 to 9) as first number otherwise we have 8 numbers(excluding x digit and 0). Then for all other digits, we have 9 choices i.e (0 to 9 excluding d digit). We simple call digitNumber function with n-1 digits as first number we already find it can be 8 or 9 and simple multiply it. For other numbers we check if digits are odd or even if it is odd we call digitNumber function with (n-1)/2 digits and multiply it by 9 otherwise we call digitNumber function with n/2 digits and store them in result and take result square.
Illustration :
Number from 1 to 7 excluding digit 9. digits multiple number 1 8 8 2 8*9 72 3 8*9*9 648 4 8*9*9*9 5832 5 8*9*9*9*9 52488 6 8*9*9*9*9*9 472392 7 8*9*9*9*9*9*9 4251528
As we can see, in each step we are half the number of digits. Suppose we have 7 digits in this we call function from main with 6(7-1) digits. when we half the digits we left with 3(6/2) digits. Because of this we have to multiply result due to 3 digits with itself to get result for 6 digits. Similarly for 3 digits we have odd digits, we have odd digits. We find result with 1 ((3-1)/2) digits and find result square and multiply it with 9, because we find result for d-1 digits.
C++
// C++ Implementation of above method #include <bits/stdc++.h> #define mod 1000000007 using namespace std; // Finding number of possible number with // n digits excluding a particular digit long long digitNumber( long long n) { // Checking if number of digits is zero if (n == 0) return 1; // Checking if number of digits is one if (n == 1) return 9; // Checking if number of digits is odd if (n % 2) { // Calling digitNumber function // with (digit-1)/2 digits long long temp = digitNumber((n - 1) / 2) % mod; return (9 * (temp * temp) % mod) % mod; } else { // Calling digitNumber function // with n/2 digits long long temp = digitNumber(n / 2) % mod; return (temp * temp) % mod; } } int countExcluding( int n, int d) { // Calling digitNumber function // Checking if excluding digit is // zero or non-zero if (d == 0) return (9 * digitNumber(n - 1)) % mod; else return (8 * digitNumber(n - 1)) % mod; } // Driver function to run above program int main() { // Initializing variables long long d = 9; int n = 3; cout << countExcluding(n, d) << endl; return 0; } |
Java
// Java Implementation of above method import java.lang.*; class GFG { static final int mod = 1000000007 ; // Finding number of possible number with // n digits excluding a particular digit static int digitNumber( long n) { // Checking if number of digits is zero if (n == 0 ) return 1 ; // Checking if number of digits is one if (n == 1 ) return 9 ; // Checking if number of digits is odd if (n % 2 != 0 ) { // Calling digitNumber function // with (digit-1)/2 digits int temp = digitNumber((n - 1 ) / 2 ) % mod; return ( 9 * (temp * temp) % mod) % mod; } else { // Calling digitNumber function // with n/2 digits int temp = digitNumber(n / 2 ) % mod; return (temp * temp) % mod; } } static int countExcluding( int n, int d) { // Calling digitNumber function // Checking if excluding digit is // zero or non-zero if (d == 0 ) return ( 9 * digitNumber(n - 1 )) % mod; else return ( 8 * digitNumber(n - 1 )) % mod; } // Driver function to run above program public static void main(String[] args) { // Initializing variables int d = 9 ; int n = 3 ; System.out.println(countExcluding(n, d)); } } // This code is contributed by Anant Agarwal. |
Python3
# Python Implementation # of above method mod = 1000000007 # Finding number of # possible number with # n digits excluding # a particular digit def digitNumber(n): # Checking if number # of digits is zero if (n = = 0 ): return 1 # Checking if number # of digits is one if (n = = 1 ): return 9 # Checking if number # of digits is odd if (n % 2 ! = 0 ): # Calling digitNumber function # with (digit-1)/2 digits temp = digitNumber((n - 1 ) / / 2 ) % mod return ( 9 * (temp * temp) % mod) % mod else : # Calling digitNumber function # with n/2 digits temp = digitNumber(n / / 2 ) % mod return (temp * temp) % mod def countExcluding(n,d): # Calling digitNumber function # Checking if excluding digit is # zero or non-zero if (d = = 0 ): return ( 9 * digitNumber(n - 1 )) % mod else : return ( 8 * digitNumber(n - 1 )) % mod # Driver code d = 9 n = 3 print (countExcluding(n, d)) # This code is contributed # by Anant Agarwal. |
C#
// C# Implementation of above method using System; class GFG { static int mod = 1000000007; // Finding number of possible number with // n digits excluding a particular digit static int digitNumber( long n) { // Checking if number of digits is zero if (n == 0) return 1; // Checking if number of digits is one if (n == 1) return 9; // Checking if number of digits is odd if (n % 2 != 0) { // Calling digitNumber function // with (digit-1)/2 digits int temp = digitNumber((n - 1) / 2) % mod; return (9 * (temp * temp) % mod) % mod; } else { // Calling digitNumber function // with n/2 digits int temp = digitNumber(n / 2) % mod; return (temp * temp) % mod; } } static int countExcluding( int n, int d) { // Calling digitNumber function // Checking if excluding digit is // zero or non-zero if (d == 0) return (9 * digitNumber(n - 1)) % mod; else return (8 * digitNumber(n - 1)) % mod; } // Driver function to run above program public static void Main() { // Initializing variables int d = 9; int n = 3; Console.WriteLine(countExcluding(n, d)); } } // This code is contributed by vt_m. |
PHP
<?php // PHP Implementation // of above method $mod = 1000000007; // Finding number of // possible number with // n digits excluding // a particular digit function digitNumber( $n ) { global $mod ; // Checking if number // of digits is zero if ( $n == 0) return 1; // Checking if number // of digits is one if ( $n == 1) return 9; // Checking if number // of digits is odd if ( $n % 2 != 0) { // Calling digitNumber // function with // (digit-1)/2 digits; $temp = digitNumber(( $n - 1) / 2) % $mod ; return (9 * ( $temp * $temp ) % $mod ) % $mod ; } else { // Calling digitNumber // function with n/2 digits $temp = digitNumber( $n / 2) % $mod ; return ( $temp * $temp ) % $mod ; } } function countExcluding( $n , $d ) { global $mod ; // Calling digitNumber // function Checking if // excluding digit is // zero or non-zero if ( $d == 0) return (9 * digitNumber( $n - 1)) % $mod ; else return (8 * digitNumber( $n - 1)) % $mod ; } // Driver code $d = 9; $n = 3; print (countExcluding( $n , $d )); // This code is contributed by // Manish Shaw(manishshaw1) ?> |
Javascript
<script> // JavaScript Implementation of above method const mod = 1000000007; // Finding number of possible number with // n digits excluding a particular digit function digitNumber(n) { // Checking if number of digits is zero if (n == 0) return 1; // Checking if number of digits is one if (n == 1) return 9; // Checking if number of digits is odd if (n % 2) { // Calling digitNumber function // with (digit-1)/2 digits let temp = digitNumber((n - 1) / 2) % mod; return (9 * (temp * temp) % mod) % mod; } else { // Calling digitNumber function // with n/2 digits let temp = digitNumber(n / 2) % mod; return (temp * temp) % mod; } } function countExcluding(n, d) { // Calling digitNumber function // Checking if excluding digit is // zero or non-zero if (d == 0) return (9 * digitNumber(n - 1)) % mod; else return (8 * digitNumber(n - 1)) % mod; } // Driver function to run above program // Initializing variables let d = 9; let n = 3; document.write(countExcluding(n, d) + "<br>" ); // This code is contributed by Surbhi Tyagi. </script> |
648
Time Complexity: O(log n), where n represents the given integer.
Auxiliary Space: O(logn), due to recursive stack space.