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 1 *(9 N-1 ) .
De manera similar, cuenta todos esos números con N dígitos y 3 ceros = N C 3 *(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 1 *(9 N-1 ) + N C 3 *(9 N-3 ) + N C 5 *(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 * (1/9)) + ( N C 3 * (1/9^3)) + ( N C 5 * (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++
// 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
// 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
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'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#
// 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 // 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 ?>
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
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)
Publicación traducida automáticamente
Artículo escrito por andrew1234 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA