Given a string of numbers and a number of multiplication operators, what is the highest number one can calculate?

Question

This was an interview question I had and I was embarrassingly pretty stumped by it. Wanted to know if anyone could think up an answer to it and provide the big O notation for it.

Question: Given a string of numbers and a number of multiplication operators, 
          what is the highest number one can calculate? You must use all operators

You cannot rearrange the string. You can only use the multiplication operators to calculate a number.

E.g. String = "312" , 1 multiplication operator

You can do 3*12 = 36 or 31*2= 62. The latter obviously being the right answer.

Answer 1

I am assuming here that the required number m of multiplication operators is given as part of the problem, along with the string s of digits.

You can solve this problem using the tabular method (aka "dynamic programming") with O(m |s|²) multiplications of numbers that are O(|s|) digits long. The optimal computational complexity of multiplication is not known, but with the schoolbook multiplication algorithm this is O(m |s|⁴) overall.

(The idea is to compute the answer for each subproblem consisting of a tail of the string and a number m′ ≤ m. There are O(m |s|) such subproblems and solving each one involves O(|s|) multiplications of numbers that are O(|s|) digits long.)

In Python, you could program it like this, using the @memoized decorator from the Python decorator library:

@memoized
def max_product(s, m):
    """Return the maximum product of digits from the string s using m
    multiplication operators.

    """
    if m == 0:
        return int(s)
    return max(int(s[:i]) * max_product(s[i:], m - 1)
               for i in range(1, len(s) - m + 1))

If you're used to the bottom-up form of dynamic programming where you build up a table, this top-down form might look strange, but in fact the @memoized decorator maintains the table in the cache property of the function:

>>> max_product('56789', 1)
51102
>>> max_product.cache
{('89', 0): 89, ('9', 0): 9, ('6789', 0): 6789, ('56789', 1): 51102, ('789', 0): 789}

Answer 2

I found the above DP solution helpful but confusing. The recurrence makes some sense, but I wanted to do it all in one table without that final check. It took me ages to debug all the indices, so I've kept some explanations.

To recap:

1. Initialize T to be of size N (because digits 0..N-1) by k+1 (because 0..k multiplications).
2. The table T(i,j) = the greatest possible product using the i+1 first digits of the string (because of zero indexing) and j multiplications.
3. Base case: T(i,0) = digits[0..i] for i in 0..N-1.
4. Recurrence: T(i,j) = max_a(T(a,j-1)*digits[a+1..i]). That is: Partition digits[0..i] in to digits[0..a]*digits[a+1..i]. And because this involves a multiplication, the subproblem has one fewer multiplications, so search the table at j-1.
5. In the end the answer is stored at T(all the digits, all the multiplications), or T(N-1,k).

The complexity is O(N²k) because maximizing over a is O(N), and we do it O(k) times for each digit (O(N)).

public class MaxProduct {

    public static void main(String ... args) {
        System.out.println(solve(args[0], Integer.parseInt(args[1])));
    }

    static long solve(String digits, int k) {
        if (k == 0)
            return Long.parseLong(digits);

        int N = digits.length();
        long[][] T = new long[N][k+1];
        for (int i = 0; i < N; i++) {
            T[i][0] = Long.parseLong(digits.substring(0,i+1));
            for (int j = 1; j <= Math.min(k,i); j++) {
                long max = Integer.MIN_VALUE;
                for (int a = 0; a < i; a++) {
                    long l = Long.parseLong(digits.substring(a+1,i+1));
                    long prod = l * T[a][j-1];
                    max = Math.max(max, prod);
                }
                T[i][j] = max;
            }
        }
        return T[N-1][k];
    }
}