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 1000000007using namespace std;// Finding number of possible number with// n digits excluding a particular digitlong 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 programint main() { // Initializing variables long long d = 9; int n = 3; cout << countExcluding(n, d) << endl; return 0;} |
Java
// Java Implementation of above methodimport java.lang.*;class GFG { static final int mod = 1000000007;// Finding number of possible number with// n digits excluding a particular digitstatic 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 programpublic 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 methodmod=1000000007# Finding number of# possible number with# n digits excluding# a particular digitdef 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 coded = 9n = 3print(countExcluding(n, d))# This code is contributed# by Anant Agarwal. |
C#
// C# Implementation of above methodusing 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 digitfunction 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> |
Output:
648
Time Complexity: O(log n), where n represents the given integer.
Auxiliary Space: O(logn), due to recursive stack space.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
