Given a number check if digits form an equation with addition?

Question

Given a string S, I want to find out whether there are non-overlapping substrings A, B and C in S, so that the equation A + B = C holds when the substrings are interpreted as decimal numbers.

Example: For S = 17512, the answer is yes, because 12 + 5 = 17 holds.

This is not a homework question, I have tried approaching this problem building a suffix array

17512

7512

512

12

2

but then I realize that given 132, 1 + 2 = 3 Would require other forms of permutations in selection?

How do you solve this in an efficient way?

Answer 1

Let S be the decimal representation of the number. If n = |S| is small enough (<500 or so), you can use the following algorithm:

Let us enumerate A and C from the equation A + B = C (where we assume w.l.o.g. A > B). We know that they need to be of around the same size (plus/minus one digit), so enumerating the possibilities is a cubic operation (there are O(n³) candidates).

For every candidate pair (A, C), we need to check whether B = C - A is in the string and not overlapping with any of the A or C substrings. We can compute the difference in linear time using arithmetics in base 10.

The tricky part is to check whether B is a substring not overlapping A or C. A and C split the string into 3 parts:

S = xAyCz

If we enumerate them in a clever way, with fixed start positions and decreasing size, we can maintain suffix automata of part x and the reverses of parts y and z.

Now we can check in linear time whether B = C - A (or its reverse) exists in one of the three parts.

Time complexity of this approach: Θ(n⁴).

There is a variation of this which is slightly more complicated, but faster (thanks to Evgeny for pointing it out):

• Create a suffix tree of the input string. Every node represents a substring. Store in every node a balanced binary search tree of the positions where the substring occurs in the string. You might need persistent trees here to save time and space.
• Enumerate A and C, but this time starting from the least-significant digit (the rightmost end).
• While growing A and C from right to left, keep track of the result of B = C - A. It will also grow from least-significant to most-siginificant digit. Do a search for B in the suffix tree. You can do this one digit at a time, so you can make grow A and C by 1 digit, update B and locate it in the suffix tree in O(1).
• If B is positive, do three range queries in the BBST of positions to check whether B occurs in the string and does not overlap A or C

Runtime: O(n³ log n).

UPDATE: regarding the simplified version where all characters need to be used:

We first realize that we can do arithmetics on substrings of our string in linear time, if we work in base 10.

Now we want to find the splitting points a < b, so that your three substrings are A = s₁...s_a, B = s_a+1...s_b and C = s_b+1...s_n.

We can prove that there is only a constant number of candidates for a and b, because all three parts must have approximately the same size for the equation to hold.

Using arbitrary precision arithmetics, we can easily try out all candidate pairs (a,b) and for each of those, find M = max(A,B,C). Then just check whether M is the sum of the other two numbers.

Total time complexity: Θ(n).