C : Sum of reverse numbers

Question

So I want to solve an exercise in C or in SML but I just can't come up with an algorithm that does so. Firstly I will write the exercise and then the problems I'm having with it so you can help me a bit.

EXERCISE

We define the reverse number of a natural number N as the natural number Nr which is produced by reading N from right to left beginning by the first non-zero digit. For example if N = 4236 then Nr = 6324 and if N = 5400 then Nr = 45.

So given any natural number G (1≤G≤10^100000) write a program in C that tests if G can occur by the sum of a natural number N and its reverse Nr. If there is such a number then the program must return this N. If there isn't then the program must return 0. The input number G will be given through a txt file consisted only by 1 line.

For example, using C, if number1.txt contains the number 33 then the program with the instruction :

> ./sum_of_reverse number1.txt

could return for example 12, because 12+21 = 33 or 30 because 30 + 3 = 33. If number1.txt contains the number 42 then the program will return 0.

Now in ML if number1.txt contains the number 33 then the program with the instruction :

sum_of_reverse "number1.txt"; 

it will return:

val it = "12" : string

The program must run in about 10 sec with a space limit : 256MB

The problems I'm having

1. At first I tried to find the patterns, that numbers with this property present. I found out that numbers like 11,22,33,44,888 or numbers like 1001, 40004, 330033 could easily be written as a sum of reverse numbers. But then I found out that these numbers seem endless because of numbers for example 14443 = 7676 + 6767 or 115950 = 36987 + 78963.

2. Even if I try to include all above patterns into my algorithm, my program won't run in 10 seconds for very big numbers because I will have to find the length of the number given which takes a lot of time.

3. Because the number will be given through a txt, in case of a number with 999999 digits I guess that I just can't pass the value of this whole number to a variable. The same with the result. I assume that you are going to save it to a txt first and then print it??

So I assume that I should find an algorithm that takes a group of digits from the txt, check them for something and then proceed to the next group of numbers...?

Answer 1

Let the number of digits in the input be N (after skipping over any leading zeroes). Then - if my analysis below is correct - the algorithm requires only ≈ N bytes of space and a single loop which runs ≈ N/2 times. No special "big number" routines or recursive functions are required.

Observations

The larger of 2 numbers that add up to this number must either:
(a) have N digits, OR
(b) have N-1 digits (in which case the first digit in the sum must be 1)

There's probably a way to handle these two scenarios as one, but I haven't thought through that. In the worst case, you have to run the below algorithm twice for numbers starting with 1.

Also, when adding the digits:

• the maximum sum of 2 digits alone is 18, meaning a max outgoing carry of 1
• even with an incoming carry of 1, the maximum sum is 19, so still a max carry of 1
• the outgoing carry is independent of the incoming carry, except when the sum of the 2 digits is exactly 9

Adding them up

In the text below, all variables represent a single digit, and adjacency of variables simply means adjacent digits (not multiplication). The ⊕ operator denotes the sum modulo 10. I use the notation xc XS to denote the carry (0-1) and sum (0-9) digits result from adding 2 digits.

Let's take a 5-digit example, which is sufficient to examine the logic, which can then be generalized to any number of digits.

  A B C D E
+ E D C B A

Let A+E = xc XS, B+D = yc YS and C+C = 2*C = zc ZS

In the simple case where all the carries are zero, the result would be the palindrome:

XS YS ZS YS XS

But because of the carries, it is more like:

xc XS⊕yc YS⊕zc ZS⊕yc YS⊕xc XS

I say "like" because of the case mentioned above where the sum of 2 digits is exactly 9. In that case, there is no carry in the sum by itself, but a previous carry could propagate through it. So we'll be more generic and write:

c5 XS⊕c4 YS⊕c3 ZS⊕c2 YS⊕c1 XS

This is what the input number must match up to - if a solution exists. If not, we'll find something that doesn't match and exit.

(Informal Logic for the) Algorithm

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

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

Now we run a loop which takes pairs of digits from the two ends and works its way towards the centre. Let's call the two digits being compared in the current iteration H and L. So the loop will compare:

• XS⊕c4 and XS
• YS⊕c3 and YS⊕c1
• etc.

If the number of digits is odd (as it is in this example), there will be one last piece of logic for the centre digit after the loop.

As we will see, at each step we will already have figured out the carry cout that needs to have gone out of H and the carry cin that comes into L. (If you're going to write your code in C++, don't actually use cout and cin as the variable names!)

Initially, we know that cout = c5 and cin = 0, and quite clearly XS = L directly (use L⊖cin in general).

Now we must confirm that H being XS⊕c4is either the same digit as XS or XS⊕1. If not, there is no solution - exit.

But if it is, so far so good, and we can calculate c4 = H⊖L. Now there are 2 cases:-

• XS is <= 8 and hence xc = cout
• XS is 9, in which case xc = 0 (since 2 digits can't add up to 19), and c5 must be equal to c4 (if not, exit)

Now we know both xc and XS. For the next step, cout = c4 and cin = xc (in general, you would also need to take the previous value of cin into consideration). Now when comparing YS⊕c3 and YS⊕c1, we already know c1 = cin and can compute YS = L⊖c1. The rest of the logic then follows as before.

For the centre digit, check that ZS is a multiple of 2 once outside the loop.

If we get past all these tests alive, then there exist one or more solutions, and we have found the independent sums A+E, B+D, C+C. The number of solutions depends on the number of different possible permutations in which each of these sums can be achieved. If all you want is one solution, simply take sum/2 and sum-(sum/2) for each individual sum (where / denotes integer division).

Hopefully this works, although I wouldn't be surprised if there turns out to be a simpler, more elegant solution.

Addendum

This problem teaches you that programming isn't just about knowing how to spin a loop, you also have to figure out the most efficient and effective loop(s) to spin after a detailed logical analysis. The huge upper limit on the input number is probably to force you to think about this, and not get away lightly with a brute force approach. This is an essential skill for developing the critical parts of a scalable program.