An `non decreasing` number is one containing no two consecutive digits (left to right), whose the first is higer than the second. For example, 1235 is an non decreasing number, 1229 is too, but 123429 isn't.

Write a function that finds the number of non decreasing numbers up to `10**N` (exclusive) where N is the input of your function. For example, if `N=3`, you have to count all non decreasing numbers from 0 to 999.

 You'll definitely need something smarter than brute force for large values of N!

Source: codewars | Difficulty: EASY
Tags: Fundamentals

Mathematics

Starter code: def increasing_numbers(n):
	

Solutions:
def increasing_numbers(d):
	s = 1
	for i in range(1, 10):
		s = s * (i + d) // i
	return s


from functools import lru_cache

@lru_cache(maxsize=None)
def f(ndigits, starting_digit):
	if ndigits == 0:
		return 1
	return sum((f(ndigits - 1, i) for i in range(starting_digit, 10)))

def increasing_numbers(digits):
	if digits == 0:
		return 1
	return sum((f(digits - 1, i) for i in range(10)))


from functools import reduce

def increasing_numbers(n):
	return reduce(int.__mul__, range(n + 1, n + 10)) // 362880


from functools import reduce
from operator import mul

def increasing_numbers(digits):
	return reduce(mul, range(digits + 1, digits + 10), 1) // 362880


from math import factorial
from functools import reduce
import operator

def increasing_numbers(digits):
	if digits == 0:
		return 1
	if digits == 1:
		return 10
	consec_pro = reduce(operator.mul, (i for i in range(10, 10 + digits)))
	return consec_pro / factorial(digits)


from math import factorial

def nCr(n, r):
	return factorial(n) // factorial(r) // factorial(n - r)

def increasing_numbers(digits):
	return nCr(digits + 9, 9)


from math import factorial

def increasing_numbers(d):
	return factorial(9 + d) / (factorial(d) * factorial(9)) if d > 0 else 1


def increasing_numbers(n):
	return fac(n + 9) / (fac(9) * fac(n))

def fac(n):
	c = 1
	for i in range(2, n + 1):
		c *= i
	return c


from math import factorial

def increasing_numbers(n):
	return factorial(n + 9) / (factorial(9) * factorial(n))


from math import factorial

def increasing_numbers(digits):
	return factorial(9 + digits) // (factorial(digits) * factorial(9))