TCHS-8-500

 

 

Problem Statement

A common task for math students is to solve 'word math' questions, where each distinct letter represents a distinct digit.
Given a list of word math numbers to add, your task is to calculate the greatest possible sum of those numbers.

For example, given the expression: TOP + CODER

the maximum sum possible by substituting numbers is: 783 + 98654 ------- 99437

with C = 9, D = 6, E = 5, O = 8, P = 3, R = 4 and T = 7.
Please note that, for this question, word math numbers are allowed to start with a zero.

Definition

Class:	WordMath
Method:	maximumSum
Parameters:	String[]
Returns:	int
Method signature:	int maximumSum(String[] summands)
(be sure your method is public)

Notes

-

Different letters must represent different digits, identical letters must represent identical digits.

-

Not all digits in the result must appear in the summands.

Constraints

-

summands will contain between 1 and 10 elements, inclusive.

-

Each element of summands will contain between 1 and 8 characters, inclusive.

-

Each element of summands will contain only uppercase letters ('A'-'Z').

-

summands will contain at most 10 distinct letters.

Examples

0)

{"TOP", "CODER"}

Returns: 99437

The example given in the problem statement.

1)

{"AAA", "AAA"}

Returns: 1998

With only one letter, the maximum sum is obtained by setting A = 9.

2)

{"A", "B", "C", "D", "E", "F", "G", "H", "I", "J"}

Returns: 45

Each letter is used once, and there are 10 different letters, so however the digits are distributed this must add up to 0 + 1 + ... + 8 + 9 = 45

3)

{"AB", "BA"}

Returns: 187

4)

{"READIEST","OPERATIC","TOPCODER","PREDICTS","RAPIDEST","ASTEROID","AIRSPEED"}

Returns: 563639653

 

import java.util.Arrays;

public class WordMath {

	int[] weigh = new int[26];

	public int maximumSum(String[] summands) {
		for (String s : summands)
			for (int j = 0, n = s.length(); j < n; j++)
				weigh[s.charAt(j) - 'A'] += Math.pow(10, n - j - 1);
		Arrays.sort(weigh);
		int ret = 0;
		for (int i = 0; i < 10; i++)
			ret += weigh[25 - i] * (9 - i);
		return ret;
	}

}