algorithm - The number prodigy : reverse sum of pattern -


number prodigy given x - there's x digit number n, reverse of n m. number prodigy interested in finding out how many x digit numbers of form : n+m=10^x-1 , n expected not have trailing zeroes. means n%10 != 0 .

in case of x=1, 9 such combinations exist.

denote a[i] - i'th digit of a.

we first need understand n+m=10^x-1, need n[i]+m[i]=9 i. since m[i]=n[x-i], means need n[i] + n[x-i] = 9. means, once n[i] set, n[x-i].

we can derive recursive formula:

f(x) = 10*f(x-2) 

the idea - @ first digit of x, have 10 possibilities it, , each possibility, set n[0] , n[x-1].

however, allows leading , trailing zeros, don't want. first , last number can 0.

g(x) = 8*f(x-2) 

the above chosing 1 of 1,2,...,8 n[0], setting (one option) last number n[x-1] = 9 - n[0], , invoke recursive call without restrictions. note neither n[0] nor n[x-1] can zero.

base clauses:

f(0) = 1  f(1) = 0  

f(1)=0 because there no natural number n such n+n=9.

all in all, found recursive formula compute total number of elements. recursive formula can transformed close 1 basic algebra. leave part you.


Comments

Popular posts from this blog

c++ - Difference between pre and post decrement in recursive function argument -

php - Nothing but 'run(); ' when browsing to my local project, how do I fix this? -

php - How can I echo out this array? -