Quick Sum TopCoder (Brute Force solution)

Question

Given a string of digits, find the minimum number of additions required for the string to equal some target number. Each addition is the equivalent of inserting a plus sign somewhere into the string of digits. After all plus signs are inserted, evaluate the sum as usual. For example, consider the string "12" (quotes for clarity). With zero additions, we can achieve the number 12. If we insert one plus sign into the string, we get "1+2", which evaluates to 3. So, in that case, given "12", a minimum of 1 addition is required to get the number 3. As another example, consider "303" and a target sum of 6. The best strategy is not "3+0+3", but "3+03". You can do this because leading zeros do not change the result.

Write a class QuickSums that contains the method minSums, which takes a String numbers and an int sum. The method should calculate and return the minimum number of additions required to create an expression from numbers that evaluates to sum. If this is impossible, return -1.

_{TopCoder link}

So I came up with a brute force solution of checking all possible solutions to find the min. Is there a better way to do this?

public class QuickSums { public static void main(String args[]) { String input = "99999"; int total = 45; int res = minSums(input, total); System.out.println(res); } // With at most 10 digits(constraint given), there are at most 2^9 ways to insert plus signs into the string. // Therefore, there are at most 2^9 possibilities to consider. We can use recursion to go through // all possibilities and keep track of the minimum number of additions required public static int minSums(String numbers, int sum) { int N = numbers.length(); // base cases if (N <= 3 && sum == Integer.parseInt(numbers)) { return 0; } else if (N == 2 && Integer.parseInt(numbers.substring(0, N - 1)) + Integer.parseInt(numbers.substring(N - 1)) == sum) { return 1; } else if (N == 2 && Integer.parseInt(numbers.substring(0, N - 1)) + Integer.parseInt(numbers.substring(N - 1)) != sum) { return -1; } else if (N == 1 && Integer.parseInt(numbers) != sum) { return -1; } // solution else { int lenOFStr = N-1; int possibleCombination = (int) Math.pow(2, lenOFStr); // numbers will contain between 1 and 10 characters, inclusive. int min = Integer.MAX_VALUE; StringBuilder tempString; for (int i = 0; i < possibleCombination; i++) { String plus = Integer.toBinaryString(i); while (plus.length() < lenOFStr) { plus = "0" + plus; } // System.out.println(plus); // Add plus sign to the string tempString = new StringBuilder(numbers); int len = N; for (int k = 0; k < lenOFStr ; k++) { if (plus.charAt(k) == '1') { len = len + 1; int offset = len-N+k; // System.out.println(offset); tempString.insert(offset, " "); } } // System.out.println(tempString); // compute the sum String[] arr = tempString.toString().split(" "); long tempSum = 0; for (String s : arr) { tempSum +=Long.parseLong(s); } // check if the sum is same if (tempSum == sum) { min = Math.min(arr.length-1, min); } } return (min == Integer.MAX_VALUE) ? -1 : min; } } } 

This program works fine for all inputs but I'm wondering, there must be a dynamic programming solution to this? Or something better?

Answer 1

public static int minSums(String numbers, int sum) { int N = numbers.length(); 

variables should be named using camelCase casing so n would be better, but what does N/n represent ? Its the number of digits contained in the String numbers which isn't named correctly because there is only one number passed which consists of multiple digits. So a better way would be like so

public static int minSums(String number, int sum) { int digits = number.length(); 

but as the default indentation is 4 spaces this should be like so

public static int minSums(String number, int sum) { int digits = number.length(); 

---

This if..else if..else construct can be simplified because for the first cases you are returning a value the else if..else aren't needed and will save some horizontal spacing if removed. You should have the two cases where you check for N == 2 into one single if with a nested if..else like so

// changed N to digits if (digits <= 3 && sum == Integer.parseInt(numbers)) { return 0; } if (digits == 2) { if (Integer.parseInt(numbers.substring(0, N - 1)) + Integer.parseInt(numbers.substring(N - 1)) == sum) { return 1; } else { return -1; } } if (digits == 1 && Integer.parseInt(numbers) != sum) { return -1; } // solution 

---

Commented out code is dead code and should be removed because it is only adding noise to the code which decreases readability.

---

Let your variables and operators have some space to breathe. Something like int offset = len-N+k; isn't just as readable as int offset = len -N + k;.

---

Answer 2

For what I see, there are a couple of things that should be improved.

---

As @Heslacher mentioned in his answer, naming should be changed into something better. I'd suggest to change:

public static int minSums(String numbers, int sum) { int N = numbers.length(); 

into something like:

public static int minSums(String digits, int sum) { int numberOfDigits = digits.length(); 

---

The current method minSums does a bit too much IMO. It parses the string and also finds the solutions. I'd split that in two parts: one which gets all the possible numbers starting from the original string and one which finds the solution based on the numbers taken from the additional method.

---

As an alternative solution, I'd suggest the following (in pseudo-code):

// this method should return all possible numbers in a string // of digits. For "1234" it should return {1,2,3,4,12,23,34,123,234} int[] getPossibleNumbers(String digits){ char[] chars = digits.toCharArray(); List<int> numbers = new List<int>(); int helper; int zero = 48; // this is the char val for the '0' digit for(int i = 0; i < chars.length; i++){ for(int j = 1; j < chars.length && (i + j) < chars.length; j++){ helper = 0; for(int k = 0; k < j; k++){ helper = (helper * 10) + ((int)chars[i + k]) - zero; } numbers.append(helper); } } return numbers.toArray(); } int minSums(String digits, int sum){ int[] numbers = getPossibleNumbers(digits); Queue<SumStatus> backupQueue = new Queue<SumStatus>(); int numbersStartingIndex; // this index will be used to get the various numbers to sum for(int i = 0; i < numbers.length; i++){ SumStatus status = new SumStatus(new List<int>().append(numbers[i]), numbers[i]); backupQueue.push(status); } while(!backupQueue.isEmpty()){ SumStatus status = backupQueue.pop(); if(status.sum == sum){ // we found the min-sum return status.numbers.length() - 1; } if(status.sum < sum){ // we have not found the min-sum yet if(status.availableNumbers.length > 0){ for(int i = 0; i < status.availableNumbers.length; i++){ SumStatus newStatus = new SumStatus(status.numbers, status.sum); newStatus.numbers.append(status.availableNumbers[i]); newStatus.sum += status.availableNumbers[i]; // copy the new available numbers (all the previously available ones except for the one in position 'i') newStatus.availableNumbers = CopyArray(status.availableNumbers, exceptIndex: i); if(newStatus.sum <= sum){ backupQueue.push(status); } } } } // when status.sum > sum the item is simply ignored and popped from the queue } // no possible combination found return -1; } class SumStatus{ List<int> numbers; int[] availableNumbers; int sum; SumStatus(List<int> nums, int currentSum){ numbers = nums; sum = currentSum; } } 

The proposed solution does a Breadth-First Search in the State Space of the problem. The State Space is made of: the numbers evaluated up to that state, the sum of the used numbers, and the available numbers (the ones not yet used). The Breadth-First Search may not be immediatly visible because there's no tree to visit in a recursive fashion, but it's implemented via a Queue<SumStatus>.

Let me know if anything is unclear.

P.S.: The code is not working code. It just serves as a means to clarify the idea I had.