WAP to Print number of not neutral numbers below 10^k mod(10^9+7)

By | 18.02.2017

WAP to Print number of not neutral numbers below 10^k mod(10^9+7)


An increasing number is a number in which values of digits increase when we go from left to right; for example,123455 . Similarly a decreasing number is a number in which values of digits decrease when we go from left to right; for example,54110 . We shall call a positive integer that is neither increasing nor decreasing a “neutral” number; for example, 151212 . As n increases, the proportion of neutral numbers below n increases such that there are 12951 numbers below one-million that are not neutral and only 277032 non-neutral numbers below 10^10.

How many numbers below 10^k are not neutral? Print the number of not neutral numbers below 10^k mod(10^9+7).


Explanation 


Input Format

First line contains an integer T which is the number of tests, next T lines contain an integer .

CONSTRAINTS

1<=T<=7

3<=k<=10

Sample Input :

3

3

5

10

Sample Output :

474

4953

277032

Time Limit:3.0 sec(s) for each input file.

Memory Limit:256 MB

Source Limit:1024 Kb


SOURCE CODE ::

import math
def binomial(n, k):
        assert 0 <= k <= n
        return math.factorial(n) // (math.factorial(k) * math.factorial(n - k))
def compute(a):
        DIGITS = a
        increasing = binomial(DIGITS + 9, 9) - 1
        decreasing = binomial(DIGITS + 10, 10) - (DIGITS + 1)
        flat = DIGITS * 9
        ans = (increasing + decreasing - flat)
        return str(ans)
a=input()
for i in range(0,a,1):
    print(compute(input()))

OUTPUT : :

 

//First Run---------------------------------------------------

3

3
474

5
4953

10
277032

//Second Run---------------------------------------------

3

4
1674

20
40059818

100
51161058134250

 

0 0 vote
Article Rating
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments