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
Post a Comment