We are given a number N. The task is to find the count of numbers which have N digits and odd number of zeroes.
Note: The number can have preceding 0’s.
Examples:
Input : N = 2 Output : Count = 18 Input : N = 3 Output : Count = 244
Suppose a number with N digits which contains only single zero. So the digits in the number as zero can be filled in only 1 way and the rest of each of the positions can be filled in 9 different ways with numbers from 1 to 9. So count of all such numbers with N digits and only 1 zero = NC1*(9N-1).
Similarly, count of all such numbers with N digits and 3 zeroes = NC3*(9N-3).
and so on.
So, count of all such numbers with N digits and odd number of zeroes will be,
NC1*(9N-1) + NC3*(9N-3) + NC5*(9N-5) +…….+ NCK*(9N-K)
Where, K is an odd number less than N.
The above equation can be written as,
(9N)((NC1 * (1/9)) + (NC3 * (1/9^3)) + (NC5 * (1/9^5)) +…
The above equation can be represented as subtraction of two series, (9N)*{(1+x)N-(1-x)N}/2, where x = 1/9
Which is equal to,
(10N - 8N)/2
Below is the implementation of the above approach:
C++
// C++ program to count numbers with N digits// which consists of odd number of 0's#include <bits/stdc++.h>using namespace std;// Function to count Numbers with N digits// which consists of odd number of 0'sint countNumbers(int N){ return (pow(10, N) - pow(8, N)) / 2;}// Driver codeint main(){ int n = 5; cout << countNumbers(n) << endl; return 0;} |
Java
// Java program to count numbers// with N digits which consists// of odd number of 0'simport java.io.*;class GFG { // Function to count Numbers // with N digits which consists // of odd number of 0's static int countNumbers(int N) { return (int)(Math.pow(10, N) - Math.pow(8, N)) / 2; } // Driver code public static void main(String[] args) { int n = 5; System.out.println(countNumbers(n)); }}// This code is contributed by Shashank |
Python3
# Python 3 program to count numbers# with N digits which consists of# odd number of 0's# Function to count Numbers with# N digits which consists of odd# number of 0'sdef countNumbers(N): return (pow(10, N) - pow(8, N)) // 2# Driver codeif __name__ == "__main__": n = 5 print(countNumbers(n))# This code is contributed# by ChitraNayal |
C#
// C# program to count numbers// with N digits which consists// of odd number of 0'susing System;class GFG { // Function to count Numbers // with N digits which consists // of odd number of 0's static int countNumbers(int N) { return (int)(Math.Pow(10, N) - Math.Pow(8, N)) / 2; } // Driver code public static void Main() { int n = 5; Console.WriteLine(countNumbers(n)); }}// This code is contributed// by Akanksha Rai(Abby_akku) |
PHP
<?php// PHP program to count numbers // with N digits which consists // of odd number of 0's// Function to count Numbers // with N digits which consists// of odd number of 0'sfunction countNumbers($N){ return (pow(10, $N) - pow(8, $N)) / 2;}// Driver code$n = 5;echo countNumbers($n) ;// This code is contributed// by Shivi_Aggarwal?> |
Javascript
<script> // Javascript program to count numbers with N digits // which consists of odd number of 0's // Function to count Numbers with N digits // which consists of odd number of 0's function countNumbers(N) { return parseInt((Math.pow(10, N) - Math.pow(8, N)) / 2, 10); } let n = 5; document.write(countNumbers(n)); // This code is contributed by divyeshrabadiya07. </script> |
33616
Note: Answer can be very large, so for N greater than 9, use modular exponentiation.
Time Complexity: O(log n)
Auxiliary Space: O(1), since no extra space has been taken.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
