Let the number of digits at the input be N (after missing any leading zeros). Then - if my analysis below is correct - the algorithm only requires & approx; N bytes of space and one loop that works & approx; N / 2 times. No special "large numbers" or recursive functions are required.
Observations
The larger of the 2 numbers that make up this number should either:
(a) have N digits, OR
(b) have N-1 digits (in this case, the first digit should be 1 in total)
There is probably a way to deal with these two scenarios as one, but I did not think about it. In the worst case, you need to execute the algorithm below twice for numbers starting with 1.
In addition, when adding numbers:
- the maximum amount of 2 digits is 18, which means the maximum outgoing carry 1
- even with incoming transfer 1, the maximum amount is 19, so anyway, the maximum transfer 1
- the outgoing transfer does not depend on the incoming transfer, unless the sum of two digits is exactly 9
Adding them
In the text below, all variables are a single digit, and the adjacency of variables simply means adjacent digits (not multiplication). The operator ⊕ denotes a sum modulo 10. I use the notation xc XS to denote the carry digits (0-1) and the sum (0-9) obtained from adding two digits.
Take an example of 5 digits, which is sufficient to study logic, which can then be generalized to any number of digits.
ABCDE + EDCBA
Let A + E = xc XS , B + D = yc YS and C + C = 2 * C = zc ZS
In the simple case, when all transfers are equal to zero, the result is a palindrome:
XS YS ZS YS XS
But due to hyphenation, it is more like:
xc XS⊕yc YS⊕zc ZS⊕yc YS⊕xc XS
I say “how” because of the case mentioned above, where the sum of 2 digits is 9. In this case, the amount itself is not transferred, but the previous transfer can be spread through it. So, we will be more generalized and write:
c5 XS⊕c4 YS⊕c3 ZS⊕c2 YS⊕c1 XS
This is what should match the input number - if there is a solution. If not, we will find something that does not match and will not work.
(Informal logic for) Algorithm
We do not need to store the number in a numeric variable, just use a character array / string. All math happens on separate digits (just use int digit = c[i] - '0' , you don't need atoi and co.)
We already know the value of c5 depending on whether we are in case (a) or (b) described above.
Now we start a cycle that takes pairs of numbers from two ends and makes its way to the center. Let me name two digits that are compared in the current iteration of H and L. Thus, the loop will compare:
XS⊕c4 and XSYS⊕c3 and YS⊕c1- and etc.
If the number of digits is odd (as in this example), after the loop there will be one last piece of logic for the central digit.
As we will see, at each step we will already consider the cout porting that should have come out of H and porting the cin that comes in L. (If you are going to write your C ++ code, don't really use cout and cin as names variables!)
Initially, we know that cout = c5 and cin = 0 and quite clearly XS = L (we usually use L⊖cin ).
Now we have to confirm that H, which is XS⊕c4 , is the same digit as XS or XS⊕1 . If not, there is no solution - exit.
But if it is so good, and we can calculate c4 = H⊖L Now there are 2 cases: -
- XS is <= 8 and therefore
xc = cout - XS is 9, and in this case
xc = 0 (since 2 digits cannot contain up to 19), and c5 should 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 also need to consider the previous cin value). Now, comparing YS⊕c3 and YS⊕c1 , we already know c1 = cin and can calculate YS = L⊖c1 . The rest of the logic follows as before.
For the center digit, check that ZS is a multiple of 2 times outside the loop.
If we pass all these tests, then one or more solutions exist, and we find 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 you want only one solution, just take sum/2 and sum-(sum/2) for each individual sum (where / denotes an integer division).
I hope this works, although I won’t be surprised if it turns out to be a simpler and more elegant solution.
Adding
This problem teaches you that programming is not only about knowing how to rotate the loop, you also need to figure out how efficient and effective the loop is after a detailed logical analysis. The huge upper limit of the input number will probably make you think about it and not get away easily with brute force. This is an important skill for developing critical parts of a scalable program.