MatchNumbersHard | Topcoder Archive

Problem Statement

Each digit can be represented using a certain number of matches. Your goal is to create the largest possible number using the matches that you have. For example, if you need 6 matches for zero, 7 matches for one, and 8 matches for two, and you have 21 matches, the largest number you can create is 210 (8 + 7 + 6 = 21 matches).

You are given a String[] matches and a String n. The i^th element (zero-indexed) of matches is the number of matches needed to represent the digit i. n is the number of matches you have. Return a String[] such that the first element is the number of digits of x (where x is the largest number that can be created), the second element contains the first 50 digits of x, and the third element contains the last 50 digits of x. If x has fewer than 50 digits, the second and third elements should each be all of x. No extra leading zeros should be added to any returned value. If n is too small to create any number, return a single zero as the number of digits and empty strings ("") as the second and third elements.

Definition

Class:: MatchNumbersHard
Method:: maxNumber
Parameters:: String[], String
Returns:: String[]
Method signature:: String[] maxNumber(String[] matches, String n)
(be sure your method is public)

Notes

It is not necessary to use all given matches. Some matches may be left unused.

Constraints

matches will contain between 1 and 10 elements, inclusive.
Each element of matches will be an integer between 1 and 10 ^ 18 (fits in a long), inclusive, with no leading zeros.
n will be an integer between 0 and 10 ^ 18 (fits in a long), inclusive, with no extra leading zeros.

Examples

{"6","7","8"}

"21"

Returns: {"3", "210", "210" }

Example from the problem statement.

{"1","7","8"}

"21"

Returns: {"15", "100000000000000", "100000000000000" }

{"1","1","1","1","1","1","1","1","1","1"}

"923372036854775807"

Returns: {"923372036854775807", "99999999999999999999999999999999999999999999999999", "99999999999999999999999999999999999999999999999999" }

A lot of nines.

{"1","923372036854775807"}

"923372036854775807"

Returns: {"1", "1", "1" }

{"1","923372036854775806"}

"923372036854775807"

Returns: {"2", "10", "10" }

{"1","5","10"}

"10"

Returns: {"6", "100000", "100000" }

```
{"1","923372036854775807"}
```
```
"923372036854775806"
```
```
Returns: {"1", "0", "0" }
```
Zero is the only digit that can be created. Note that no extra leading zeros should be added to any returned value.

{"1", "10"}

"1000000"

Returns: {"999991", "10000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000" }

There are 999990 zeros in the created number, so its last 50 digits are all zeros.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.