largest-multiple-of-three

< Previous 　　　　　　　　　　　　　　　　 Next >

1363. Largest Multiple of Three (Hard)

Given an integer array of digits, return the largest multiple of three that can be formed by concatenating some of the given digits in any order.

Since the answer may not fit in an integer data type, return the answer as a string.

If there is no answer return an empty string.

 

Example 1:

Input: digits = [8,1,9]
Output: "981"

Example 2:

Input: digits = [8,6,7,1,0]
Output: "8760"

Example 3:

Input: digits = [1]
Output: ""

Example 4:

Input: digits = [0,0,0,0,0,0]
Output: "0"

 

Constraints:

• 1 <= digits.length <= 10^4
• 0 <= digits[i] <= 9
• The returning answer must not contain unnecessary leading zeros.

Related Topics

[Math] [Dynamic Programming]

Hints

Hint 1

A number is a multiple of three if and only if its sum of digits is a multiple of three.

Hint 2

Use dynamic programming.

Hint 3

To find the maximum number, try to maximize the number of digits of the number.

Hint 4

Sort the digits in descending order to find the maximum number.