Cuente números con N dígitos que consisten en un número impar de 0

Nos dan un número N. La tarea es encontrar el conteo de números que tienen N dígitos y un número impar de ceros. 
Nota : el número puede tener 0 anteriores.

Ejemplos : 

Input : N = 2
Output : Count = 18

Input : N = 3
Output : Count = 244

Supongamos un número con N dígitos que contiene solo un cero. Entonces, los dígitos en el número como cero se pueden completar de una sola manera y el resto de cada una de las posiciones se puede completar de 9 formas diferentes con números del 1 al 9. Entonces cuente todos esos números con N dígitos y solo 1 cero = ^norte C ₁ *(9 ^N-1 ) .

De manera similar, cuenta todos esos números con N dígitos y 3 ceros = ^N C ₃ *(9 ^N-3 ) .
y así.

Entonces, el conteo de todos esos números con N dígitos y un número impar de ceros será, 

^N C ₁ *(9 ^N-1 ) + ^N C ₃ *(9 ^N-3 ) + ^N C ₅ *(9 ^N-5 ) +…….+ ^N C _K *(9 ^N-K )
Donde, K es un número impar menor que N. 

La ecuación anterior se puede escribir como, 

(9 ^N )(( ^N C ₁ * (1/9)) + ( ^N C ₃ * (1/9^3)) + ( ^N C ₅ * (1/9^5)) +… 
 

La ecuación anterior se puede representar como la resta de dos series, (9 ^N )*{(1+x) ^N -(1-x) ^N }/2, donde x = 1/9
Que es igual a, 

(10N - 8N)/2

A continuación se muestra la implementación del enfoque anterior: 

// 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's
int countNumbers(int N)
{
    return (pow(10, N) - pow(8, N)) / 2;
}
 
// Driver code
int main()
{
    int n = 5;
 
    cout << countNumbers(n) << endl;
 
    return 0;
}

// Java program to count numbers
// with N digits which consists
// of odd number of 0's
import 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

# 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's
 
 
def countNumbers(N):
 
    return (pow(10, N) - pow(8, N)) // 2
 
 
# Driver code
if __name__ == "__main__":
 
    n = 5
 
    print(countNumbers(n))
 
# This code is contributed
# by ChitraNayal

// C# program to count numbers
// with N digits which consists
// of odd number of 0's
using 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 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 (pow(10, $N) -
            pow(8, $N)) / 2;
}
 
// Driver code
$n = 5;
 
echo countNumbers($n) ;
 
// This code is contributed
// by Shivi_Aggarwal
?>

<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

Nota : la respuesta puede ser muy grande, por lo que para N mayor que 9, use exponenciación modular .

Complejidad temporal: O(log n)
Espacio auxiliar: O(1)