Problem Statement
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
{"TOP", "CODER"}
Returns: 99437
The example given in the problem statement.
{"AAA", "AAA"}
Returns: 1998
With only one letter, the maximum sum is obtained by setting A = 9.
{"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
{"AB", "BA"}
Returns: 187
{"AEGILOPS"}
Returns: 98765432
alphabetic order
{"SPOONFED"}
Returns: 98776543
reverse alphabetic order
{"AAAAAAAA", "AAAAAAAA", "AAAAAAAA", "AAAAAAAA", "AAAAAAAA", "AAAAAAAA", "AAAAAAAA", "AAAAAAAA", "AAAAAAAA", "BBBBBBBB"}
Returns: 988888879
{"T"}
Returns: 9
{"TCHS","SRM","EIGHT"}
Returns: 106595
{"KENNST","MICH","NOCH"}
Returns: 1001682
{"SATOR","AREPO","TENET","OPERA","ROTAS"}
Returns: 383545
{"BUENA","SUERTE"}
Returns: 1065178
{"OMG","LOL","HAKZOR","ROFL"}
Returns: 994845
{"DO","PEOPLE","READ","THESE"}
Returns: 1067585
{"TWO","SEVEN","OFF","SUIT"}
Returns: 109356
{"ONE","TWO","THREE","FOUR","NINE","TEN"}
Returns: 114733
{"IF","IT","IS","TO","BE","IT","IS","UP","TO","ME"}
Returns: 825
{"CPP","JAVA","CSHARP","VB"}
Returns: 995042
{"ZBBBBBBB","YBBBBBBB","XBBBBBBB","WBBBBBBB","VBBBBBBB","UBBBBBBB","TBBBBBBB","SBBBBBBB","RBBBBBBB"}
Returns: 450000000
breaks those who assign 9 to a first digit
{"READIEST","OPERATIC","TOPCODER","PREDICTS","RAPIDEST","ASTEROID","AIRSPEED"}
Returns: 563639653
{"XMQME", "EXXMMXQM", "EXQM", "MXXQMEM", "QXQE"}
Returns: 106869079
40 random cases
{"NSLVU", "U", "U", "U", "VWLSIV", "BN"}
Returns: 1062285
{"XPCVC", "DOXPD", "QCV", "OCXPOPDX", "C", "ODQ", "XOQ", "XO"}
Returns: 98908578
{"LLRJLJ", "JVRLRRJR", "VJL", "RL"}
Returns: 99454639
{"YV", "YVV", "V", "VYVVY"}
Returns: 99995
{"CCCXCXXX", "XCXC", "CXXXCCC", "CCCXXCC"}
Returns: 119886775
{"KK", "QZOZWQ"}
Returns: 987925
{"PP", "IIIIIPPP", "I", "IPPII"}
Returns: 100098884
{"PELGI", "E", "I", "E", "GIEI", "PGIGP"}
Returns: 204971
{"YI", "Y", "YIY", "IIYIIY", "IYYIYYY", "I", "IIIIIY"}
Returns: 11889888
{"XLLLX", "XLXLLLLX", "LXL", "XLL", "XL"}
Returns: 99089762
{"I", "UYITIYIG", "G", "IUTUTUYY"}
Returns: 187565775
{"XX", "XXXXXX", "XXX", "X"}
Returns: 1001106
{"RFFXQ", "QX"}
Returns: 98943
{"PPPPPPP", "P", "PPPPPPPP", "PPPPPP", "PPPPP", "PPPPPPP"}
Returns: 121100004
{"KPPP", "PGGZG", "PZ", "P"}
Returns: 106972
{"RMMMAMRA", "AMF", "MMFFRRR", "EF"}
Returns: 107765639
{"FGFD", "GFZGSGSS", "GZGDFGZG", "FZZDDD", "ZSZZSS", "DG", "GSZS"}
Returns: 198530096
{"QQXQYQ", "XK"}
Returns: 999065
{"YYHJHUK", "HXMAKM", "OMKX", "KH", "YMHAYAXK", "JXKOMA", "AMAUJ", "MOXAH"}
Returns: 110272991
{"LL", "CLLLDAV", "D", "ULXXX", "XARXC", "XVUXD", "LLV"}
Returns: 10108058
{"ZAXQQ", "QIANZQN", "NNVANA", "VYZN", "ZQBX"}
Returns: 10719863
{"WCGPVWC", "CVC", "WWVCPVWP", "GWCVV", "VCVPPGVC", "GGCPWCV", "PGCVPPW", "WGVWCPCG"}
Returns: 307909045
{"NLYNR", "YRYA", "AYALAANY", "NRLYRRRA", "N", "NRNLYR", "LANYR", "NNAR"}
Returns: 185577669
{"BBBBBBBB", "BBB", "BBBBBBBB", "B", "BBBBBB", "BBBBBBB", "BBBBBB"}
Returns: 212001003
{"KKK", "KK", "KKK"}
Returns: 2097
{"NIZYDMON", "ZODG", "DMYYII", "DNNMNDZY", "NONMIZ", "ZIO", "OGN"}
Returns: 189409840
{"QHQ", "E", "VVEVDT"}
Returns: 999729
{"HD", "GDGED", "D", "DHDTHH", "TD"}
Returns: 1069693
{"BOLO", "CL", "LJTLIB"}
Returns: 994581
{"WXWNGM", "WG", "MGNNM", "MANZ", "W", "XGX", "F"}
Returns: 1075453
{"JWWRWO"}
Returns: 988786
{"EEEOEOE", "OOEEE", "EEOOE", "OEEO", "EOE", "OEEEEOE", "OOOEO", "EE", "E"}
Returns: 19286859
{"MXMMXN", "XNNNXMXM", "NXXX", "XM", "NNMNM", "NN", "MXM"}
Returns: 99786363
{"ZBBZRR"}
Returns: 988977
{"OUDU", "UOGO", "OO"}
Returns: 18946
{"PKNDYK", "GDKYYDU", "K", "PDGU", "PUYGUY", "NQPYK", "GYKY"}
Returns: 11544052
{"W", "WWW", "W", "WRWWWRRR", "RWWR", "RWW", "RRWRRWW", "RRR"}
Returns: 107910589
{"ACII", "TATTRRGA", "TRMAC", "CMGTM", "R", "MTRAI", "MRTM", "MRC"}
Returns: 99255405
{"NNNUUGOW", "BNJWBJW", "UW", "NWNNWGNB", "O", "UPOWGWU", "BWPJJOJJ"}
Returns: 300993072
{"READIEST", "OPERATIC", "TOPCODER", "PREDICTS", "RAPIDEST", "ASTEROID", "AIRSPEED" }
Returns: 563639653
{"ABCDEF", "FEDCBA", "DCABEF", "EDCBAF", "BDECAF", "FFABCD" }
Returns: 4856789
{"AAAAAAAA", "BBBBBBBB", "CCCCCCC", "DDDDDDDD", "EEEEEEEE", "FFFFFFFF", "GGGGGGGG", "HHHHHHHH", "IIIIIIII", "KKKKKKKK" }
Returns: 499999995
{"HDIDGIJA", "CFGDCDDC", "EHDBIBDJ", "FHHDBJDE", "DEHHFIBG", "HFJGDBEF", "FFCEBIBE", "GFEBCIJJ", "IACJAHFA", "HADBCEDD" }
Returns: 753052982