Programa de Python para contar números que no rebotan

Si cualquier número se representa de tal manera que cuando lo leemos de izquierda a derecha, cada i ^-ésimo dígito es mayor o igual que el i-1- ^ésimo dígito, se conoce como un número creciente. Y si los dígitos de cualquier número disminuyen de izquierda a derecha, se conoce como número decreciente.

Ejemplo:

Número creciente? 235668 

todos los dígitos de izquierda a derecha son mayores o iguales al dígito anterior.

número decreciente? 653221 

todos los dígitos de izquierda a derecha son menores o iguales que el dígito anterior.

Pero si el número no es ni creciente ni decreciente se lo conoce como número hinchable .

Ejemplo:

523469 -> Algunos dígitos de izquierda a derecha disminuyen de izquierda a derecha y otros aumentan. Así que este es el ejemplo de Bouncy Number. 

La tarea en este artículo es contar el número total de números que no rebotan por debajo de 10 ^k e imprimir el recuento final en mod (10 ⁹ +7). Para hacer esto, usaremos el método de estrellas y barras para calcular la cantidad de números que no rebotan en el rango dado.

Método de estrellas y barras:

El método de barras y estrellas es una técnica que se utiliza para tratar problemas basados ​​en combinaciones. Este tipo de problemas surge cuando queremos el número de grupos idénticos.

La fórmula para calcular grupos idénticos:

Donde N son los objetos idénticos y M es el contenedor o rango. 

Fórmula definitiva:

Ejemplos:

Input : k = 6
Output : 12951
 
Input : k = 9
Output : 140906

A continuación se muestra la implementación:

# import redunce function from functools
from functools import reduce
 
 
# define a function to
# calculate nCr
def nCr(n, k):
 
  # this approach is based on
  # approach of stars and bar method
  # using reduce and lambda function
  # to calculate number & denom
  number = reduce(lambda x, y: x * y,
                 list(range(n, n - k, -1)))   
  denom = reduce(lambda x, y: x * y,
                 list(range(1, k + 1)))       
   
  #  denom root of number will be the final result
  return number // denom       
 
# Driver Code
# input value of k
k = 6 
   
# calculating r using function call
r = int((nCr(k + 10, 10) +
         nCr(k + 9, 9)
         - 2 - 10 * k))
 
# print final result
print(r % (1000000000 + 7))       

Producción:

12951