algorithm - C : Sum of reverse numbers -

so want solve exercise in c or in sml can't come algorithm so. firstly write exercise , problems i'm having can me bit.

exercise

we define reverse number of natural number n natural number nr produced reading n right left beginning first non-zero digit. example if n = 4236 nr = 6324 , if n = 5400 nr = 45.

so given natural number g (1≤g≤10^100000) write program in c tests if g can occur sum of natural number n , reverse nr. if there such number program must return n. if there isn't program must return 0. input number g given through txt file consisted 1 line.

for example, using c, if number1.txt contains number 33 program instruction :

> ./sum_of_reverse number1.txt 

could return example 12, because 12+21 = 33 or 30 because 30 + 3 = 33. if number1.txt contains number 42 program return 0.

now in ml if number1.txt contains number 33 program instruction :

sum_of_reverse "number1.txt";  

it return:

val = "12" : string 

the program must run in 10 sec space limit : 256mb

the problems i'm having

1. at first tried find patterns, numbers property present. found out numbers 11,22,33,44,888 or numbers 1001, 40004, 330033 written sum of reverse numbers. found out these numbers seem endless because of numbers example 14443 = 7676 + 6767 or 115950 = 36987 + 78963.

2. even if try include above patterns algorithm, program won't run in 10 seconds big numbers because have find length of number given takes lot of time.

3. because number given through txt, in case of number 999999 digits guess can't pass value of whole number variable. same result. assume going save txt first , print it??

so assume should find algorithm takes group of digits txt, check them , proceed next group of numbers...?

let number of digits in input n (after skipping on leading zeroes). - if analysis below correct - algorithm requires ≈ n bytes of space , single loop runs ≈ n/2 times. no special "big number" routines or recursive functions required.

observations

the larger of 2 numbers add number must either:
(a) have n digits, or
(b) have n-1 digits (in case first digit in sum must 1)

there's way handle these 2 scenarios one, haven't thought through that. in worst case, have run below algorithm twice numbers starting 1.

also, when adding digits:

• the maximum sum of 2 digits alone 18, meaning max outgoing carry of 1
• even incoming carry of 1, maximum sum 19, still max carry of 1
• the outgoing carry independent of incoming carry, except when sum of 2 digits 9

adding them up

in text below, variables represent single digit, , adjacency of variables means adjacent digits (not multiplication). ⊕ operator denotes sum modulo 10. use notation xc xs denote carry (0-1) , sum (0-9) digits result adding 2 digits.

let's take 5-digit example, sufficient examine logic, can generalized number of digits.

  b c d e + e d c b 

let a+e = xc xs, b+d = yc ys , c+c = 2*c = zc zs

in simple case carries zero, result palindrome:

xs ys zs ys xs

but because of carries, more like:

xc xs⊕yc ys⊕zc zs⊕yc ys⊕xc xs

i "like" because of case mentioned above sum of 2 digits 9. in case, there no carry in sum itself, previous carry propagate through it. we'll more generic , write:

c5 xs⊕c4 ys⊕c3 zs⊕c2 ys⊕c1 xs

this input number must match - if solution exists. if not, we'll find doesn't match , exit.

(informal logic the) algorithm

we don't need store number in numeric variable, use character array / string. math happens on single digits (just use int digit = c[i] - '0', no need atoi & co.)

we know value of c5 based on whether we're in case (a) or (b) described above.

now run loop takes pairs of digits 2 ends , works way towards centre. let's call 2 digits being compared in current iteration h , l. loop compare:

• xs⊕c4 , xs
• ys⊕c3 , ys⊕c1
• etc.

if number of digits odd (as in example), there 1 last piece of logic centre digit after loop.

as see, @ each step have figured out carry cout needs have gone out of h , carry cin comes l. (if you're going write code in c++, don't use cout , cin variable names!)

initially, know cout = c5 , cin = 0, , quite xs = l directly (use l⊖cin in general).

now must confirm h being xs⊕c4is either same digit xs or xs⊕1. if not, there no solution - exit.

but if is, far good, , can calculate c4 = h⊖l. there 2 cases:-

• xs <= 8 , hence xc = cout
• xs 9, in case xc = 0 (since 2 digits can't add 19), , c5 must equal c4 (if not, exit)

now know both xc , xs. next step, cout = c4 , cin = xc (in general, need take previous value of cin consideration). when comparing ys⊕c3 , ys⊕c1, know c1 = cin , can compute ys = l⊖c1. rest of logic follows before.

for centre digit, check zs multiple of 2 once outside loop.

if past these tests alive, there exist 1 or more solutions, , have found independent sums a+e, b+d, c+c. number of solutions depends on number of different possible permutations in each of these sums can achieved. if want 1 solution, take sum/2 , sum-(sum/2) each individual sum (where / denotes integer division).

hopefully works, although wouldn't surprised if there turns out simpler, more elegant solution.

addendum

this problem teaches programming isn't knowing how spin loop, have figure out efficient , effective loop(s) spin after detailed logical analysis. huge upper limit on input number force think this, , not away lightly brute force approach. essential skill developing critical parts of scalable program.