QuickSums (topcoder)

Just solved my first Division 2 Hard problem! (from Topcoder Single Round Match 197, division 2 hard)

Problem (abridged): Given a string numbers of digits (such as “12” or “28475”) find the minimum number of insertions of addition signs into the string so that the resulting expression evaluates to a given number sum. If this is not possible, return -1. Resulting terms in the expression are not affected by leading zeros (so 047 reads as 47).

numbers has at most 10 characters (all digits), and sum is at most 100.

Examples:

1) numbers = “1583”, sum = 161. The minimum is 1; we can just do 158+3=161.

2) numbers = “26007”, sum = 15. The minimum is 2; we do not do 2+6+0+0+7 but instead 2+6+007=2+6+7.

3) numbers = “999999”, sum = 8. Obviously impossible, so -1.

Solution: Since numbers has at most 10 digits, at most 9 spaces are available for plus signs and we can just brute force, since is very small. There seems to also be a dynamic programming solution, which I didn’t think of.

So many stumbles in this problem:

• When getting rid of the leading zeros in the expression fragments the first time, I just copied over all the nonzero characters. This is a problem if the string is something like “000”.
• Sometimes the sum of the expression being tested doesn’t fit in a 32-bit integer. Since sum isn’t supposed to be more than 100, I just broke if any of the fragments (without leading zeros!) were longer than 3 characters.
• When doing the above, I accidentally put the <testing longer than 3  characters> before removing the leading zeros, which is a problem if the string is something like “0004”, which is clearly not more than 100.

import java.util.*;

public class QuickSums {
	static int n, min, des, numplus;
	static boolean plus[];
	static String nums;

	public int minSums(String numbers, int sum) {
		n = numbers.length();
		des = sum;
		numplus = 0;
		nums = new String(numbers);
		plus = new boolean[n-1];
		min = n;
		genPlus(0);
		if (min < n) return min;
		return -1;
	}

	void genPlus(int i) {
		if (i + 1 < n) {
			plus[i] = true;
			numplus++;
			genPlus(i+1);
			plus[i] = false;
			numplus--;
			genPlus(i+1);
		} else {
			String manip = ""; manip += nums.substring(0, 1);
			for (int j = 1; j < n; j++) {
				if (plus[j-1]) manip += "+";
				manip += nums.substring(j, j+1);
			}

			// compute sum
			int s = 0;
			StringTokenizer k = new StringTokenizer(manip,"+");
			while (k.hasMoreTokens()) {
				String st = k.nextToken();
				for (int a = 0; a < st.length(); a++) { 					if (st.charAt(a) != '0')  { 						st = st.substring(a); 						break; 					} 				} 				if (st.charAt(0) == '0') st = "0"; 				if (st.length() > 3) { s = -1; break; }
				s += Integer.parseInt(st);
			}
			if (s == des) { min = Math.min(min, numplus); System.out.println(manip); }
		}
	}
}