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

This implementation is for @lars.

from __future__ import (print_function)
import collections
import sys

try:
    xrange
except NameError:  # python3
    xrange = range


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

    """
    # Guard condition.
    if len(s) <= n:
        return None

    # A type for our partial solutions.
    partial_solution = collections.namedtuple("product",
                                              ["value", "expression"])

    # Initialize the best_answers dictionary with the leading terms
    best_answers = {}
    for i in xrange(len(s)):
        term = s[0: i+1]
        best_answers[i+1] = partial_solution(int(term), term)

    # We then replace best_answers n times.
    for prev_product_count in [x for x in xrange(n)]:
        product_count = prev_product_count + 1
        old_best_answers = best_answers
        best_answers = {}
        # For each position, find the best answer with the last * there.
        for position in xrange(product_count+1, len(s)+1):
            candidates = []
            for old_position in xrange(product_count, position):
                prior_product = old_best_answers[old_position]
                term = s[old_position:position]
                value = prior_product.value * int(term)
                expression = prior_product.expression + "*" + term
                candidates.append(partial_solution(value, expression))
            # max will choose the biggest value, breaking ties by the expression
            best_answers[position] = max(candidates)

    # We want the answer with the next * going at the end of the string.
    return best_answers[len(s)]

print(max_product(sys.argv[1], int(sys.argv[2])))

Here is a sample run:

$ python mult.py 99287 2
product(value=72036, expression='9*92*87')

Hopefully the logic is clear from the implementation.

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];
    }
}

Answer 3

Yet another Java implementation. This is DP top down, aka memoization. It also prints out the actual components besides the max product.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class MaxProduct {

    private static Map<Key, Result> cache = new HashMap<>();

    private static class Key {
        int operators;
        int offset;

        Key(int operators, int offset) {
            this.operators = operators;
            this.offset = offset;
        }

        @Override
        public int hashCode() {
            final int prime = 31;
            int result = 1;
            result = prime * result + offset;
            result = prime * result + operators;
            return result;
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj) {
                return true;
            }
            if (obj == null) {
                return false;
            }
            if (!(obj instanceof Key)) {
                return false;
            }
            Key other = (Key) obj;
            if (offset != other.offset) {
                return false;
            }
            if (operators != other.operators) {
                return false;
            }
            return true;
        }
    }

    private static class Result {
        long product;
        int offset;
        Result prev;

        Result (long product, int offset) {
            this.product = product;
            this.offset = offset;
        }

        @Override
        public String toString() {
            return "product: " + product + ", offset: " + offset;
        }
    }

    private static void print(Result result, String input, int operators) {
        System.out.println(operators + " multiplications on: " + input);
        Result current = result;
        System.out.print("Max product: " + result.product + " = ");
        List<Integer> insertions = new ArrayList<>();
        while (current.prev != null) {
            insertions.add(current.offset);
            current = current.prev;
        }

        List<Character> inputAsList = new ArrayList<>();
        for (char c : input.toCharArray()) {
            inputAsList.add(c);
        }

        int shiftedIndex = 0;
        for (int insertion : insertions) {
            inputAsList.add(insertion + (shiftedIndex++), '*');
        }

        StringBuilder sb = new StringBuilder();
        for (char c : inputAsList) {
            sb.append(c);
        }

        System.out.println(sb.toString());
        System.out.println("-----------");
    }

    public static void solve(int operators, String input) {
        cache.clear();
        Result result = maxProduct(operators, 0, input);
        print(result, input, operators);
    }

    private static Result maxProduct(int operators, int offset, String input) {
        String rightSubstring = input.substring(offset);

        if (operators == 0 && rightSubstring.length() > 0) return new Result(Long.parseLong(rightSubstring), offset);
        if (operators == 0 && rightSubstring.length() == 0) return new Result(1, input.length() - 1);

        long possibleSlotsForFirstOperator = rightSubstring.length() - operators;
        if (possibleSlotsForFirstOperator < 1) throw new IllegalArgumentException("too many operators");

        Result maxProduct = new Result(-1, -1);
        for (int slot = 1; slot <= possibleSlotsForFirstOperator; slot++) {
            long leftOperand = Long.parseLong(rightSubstring.substring(0, slot));
            Result rightOperand;
            Key key = new Key(operators - 1, offset + slot);
            if (cache.containsKey(key)) {
                rightOperand = cache.get(key);
            } else {
                rightOperand = maxProduct(operators - 1, offset + slot, input);
            }

            long newProduct = leftOperand * rightOperand.product;
            if (newProduct > maxProduct.product) {
                maxProduct.product = newProduct;
                maxProduct.offset = offset + slot;
                maxProduct.prev = rightOperand;
            }
        }

        cache.put(new Key(operators, offset), maxProduct);
        return maxProduct;
    }

    public static void main(String[] args) {
        solve(5, "1826456903521651");
        solve(1, "56789");
        solve(1, "99287");
        solve(2, "99287");
        solve(2, "312");
        solve(1, "312");
    }

}

Bonus: a bruteforce implementation for anyone interested. Not particularly clever but it makes the traceback step straightforward.

import java.util.ArrayList;
import java.util.List;

public class MaxProductBruteForce {

    private static void recurse(boolean[] state, int pointer, int items, List<boolean[]> states) {
        if (items == 0) {
            states.add(state.clone());
            return;
        }

        for (int index = pointer; index < state.length; index++) {
            state[index] = true;
            recurse(state, index + 1, items - 1, states);
            state[index] = false;
        }
    }

    private static List<boolean[]> bruteForceCombinations(int slots, int items) {
        List<boolean[]> states = new ArrayList<>(); //essentially locations to insert a * operator
        recurse(new boolean[slots], 0, items, states);
        return states;
    }

    private static class Tuple {
        long product;
        List<Long> terms;

        Tuple(long product, List<Long> terms) {
            this.product = product;
            this.terms = terms;
        }

        @Override
        public String toString() {
            return product + " = " + terms.toString();
        }
    }

    private static void print(String input, int operators, Tuple result) {
        System.out.println(operators + " multiplications on: " + input);
        System.out.println(result.toString());
        System.out.println("---------------");
    }

    public static void solve(int operators, String input) {
        Tuple result = maxProduct(input, operators);
        print(input, operators, result);
    }

    public static Tuple maxProduct(String input, int operators) {
        Tuple maxProduct = new Tuple(-1, null);

        for (boolean[] state : bruteForceCombinations(input.length() - 1, operators)) {
            Tuple newProduct = getProduct(state, input);
            if (maxProduct.product < newProduct.product) {
                maxProduct = newProduct;
            }
        }

        return maxProduct;
    }

    private static Tuple getProduct(boolean[] state, String input) {
        List<Long> terms = new ArrayList<>();
        List<Integer> insertLocations = new ArrayList<>();
        for (int i = 0; i < state.length; i++) {
            if (state[i]) insertLocations.add(i + 1);
        }

        int prevInsert = 0;
        for (int insertLocation : insertLocations) {
            terms.add(Long.parseLong(input.substring(prevInsert, insertLocation))); //gradually chop off the string
            prevInsert = insertLocation;
        }

        terms.add(Long.parseLong(input.substring(prevInsert))); //remaining of string

        long product = 1;
        for (long term : terms) {
            product = product * term;
        }

        return new Tuple(product, terms);
    }

    public static void main(String[] args) {
        solve(5, "1826456903521651");
        solve(1, "56789");
        solve(1, "99287");
        solve(2, "99287");
        solve(2, "312");
        solve(1, "312");
    }

}

Answer 4

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 5

Here's an iterative dynamic programming solution.

As opposed to the recursive version (which should have a similar running time).

The basic idea:

A[position][count] is the highest number that can be obtained ending at position position, using count multiplications.

So:

A[position][count] = max(for i = 0 to position
                           A[i][count-1] * input.substring(i, position))

Do this for each position and each count, then multiply each of these at the required number of multiplications with the entire remaining string.

Complexity:

Given a string |s| with m multiplication operators to be inserted...

O(m|s|2g(s)) where g(s) is the complexity of multiplication.

Java code:

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

  // Preprocessing - set up substring values
  long[][] substrings = new long[digits.length()][digits.length()+1];
  for (int i = 0; i < digits.length(); i++)
  for (int j = i+1; j <= digits.length(); j++)
     substrings[i][j] = Long.parseLong(digits.substring(i, j));

  // Calculate multiplications from the left
  long[][] A = new long[digits.length()][multiplications+1];
  A[0][0] = 1;
  for (int i = 1; i < A.length; i++)
  {
     A[i][0] = substrings[0][i];
     for (int j = 1; j < A[0].length; j++)
     {
        long max = -1;
        for (int i2 = 0; i2 < i; i2++)
        {
           long l = substrings[i2][i];
           long prod = l * A[i2][j-1];
           max = Math.max(max, prod);
        }
        A[i][j] = max;
     }
  }

  // Multiply left with right and find maximum
  long max = -1;
  for (int i = 1; i < A.length; i++)
  {
     max = Math.max(max, substrings[i][A.length] * A[i][multiplications]);
  }
  return max;
}

A very basic test:

System.out.println(solve("99287", 1));
System.out.println(solve("99287", 2));
System.out.println(solve("312", 1));

Prints:

86304
72036
62

Yes, it just prints the maximum. It's not too difficult to have it actually print the sums, if required.

Answer 6

here's another Java solution. (I know it's correct for "312" and 1 multiplication and I think it works for others...

You'll have to remember how to obtain the complexity of recursive methods on your own, haha.

package test;

import java.util.ArrayList;
import java.util.List;

public class BiggestNumberMultiply {

    private static class NumberSplit{
        String[] numbers;
        long result;
        NumberSplit(String[] numbers){
            this.numbers=numbers.clone();
            result=1;
            for(String n:numbers){
                result*=Integer.parseInt(n);
            }
        }
        @Override
        public String toString() {
            StringBuffer sb=new StringBuffer();
            for(String n:numbers){
                sb.append(n).append("*");
            }
            sb.replace(sb.length()-1, sb.length(), "=")
                .append(result);
            return sb.toString();
        }
    }

    public static void main(String[] args) {
        String numbers = "312";
        int numMults=1;

        int numSplits=numMults;

        List<NumberSplit> splits = new ArrayList<NumberSplit>();
        splitNumbersRecursive(splits, new String[numSplits+1], numbers, numSplits);
        NumberSplit maxSplit = splits.get(0);
        for(NumberSplit ns:splits){
            System.out.println(ns);
            if(ns.result>maxSplit.result){
                maxSplit = ns;
            }
        }
        System.out.println("The maximum is "+maxSplit);
    }

    private static void splitNumbersRecursive(List<NumberSplit> list, String[] splits, String numbers, int numSplits){
        if(numSplits==0){
            splits[splits.length-1] = numbers;
            return;
        }
        for(int i=1; i<=numbers.length()-numSplits; i++){
            splits[splits.length-numSplits-1] = numbers.substring(0,i);
            splitNumbersRecursive(list, splits, numbers.substring(i), numSplits-1);
            list.add(new NumberSplit(splits));
        }
    }
}

Answer 7

The java version, though Python already showed its functional advantage and beat me:

private static class Solution {
    BigInteger product;
    String expression;
}

private static Solution solve(String digits, int multiplications) {
    if (digits.length() < multiplications + 1) {
        return null; // No solutions
    }
    if (multiplications == 0) {
        Solution solution = new Solution();
        solution.product = new BigInteger(digits);
        solution.expression = digits;
        return solution;
    }
    // Position of first '*':
    Solution max = null;
    for (int i = 1; i < digits.length() - (multiplications - 1); ++i) {
        BigInteger n = new BigInteger(digits.substring(0, i));
        Solution solutionRest = solve(digits.substring(i), multiplications - 1);
        n = n.multiply(solutionRest.product);
        if (max == null || n.compareTo(max.product) > 0) {
            solutionRest.product = n;
            solutionRest.expression = digits.substring(0, i) + "*"
                + solutionRest.expression;
            max = solutionRest;
        }
    }
    return max;
}

private static void test(String digits, int multiplications) {
    Solution solution = solve(digits, multiplications);
    System.out.printf("%s %d -> %s = %s%n", digits, multiplications,
            solution.expression, solution.product.toString());
}

public static void main(String[] args) {
    test("1826456903521651", 5);
}

Output

1826456903521651 5 -> 182*645*6*903*521*651 = 215719207032420

Answer 8

I'm pretty sure that the answer is to simply put the *s right before the biggest digits, so that the largest digit have the biggest impact. For example, if we have

 1826456903521651 

and we have five multiplications, this would be the answer.

 1*82*645*6*903521*651 

So the running time would be linear.

Edit: Okay, so this is wrong. We have two counterexamples.

Answer 9

This came to mind, it's the brute force approach influenced by the bars and stars problem.

Let's say our number is "12345" and we have 2 * operators we need to use. We can look at the string 12345 as

1_2_3_4_5

Where we can put the two * operators on any of the underscores. Since there are 4 underscores and 2 * operators, there are 4 choose 2 (or 6) different ways to place the operators. Compare those 6 possibilities and grab the largest number. A similar approach can be used for larger strings and larger number of * operators.