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

Solution: Greedy + Math + Counting sort

Count the numbers of each digit.
if sum % 3 == 0, we can use all digits.
if sum % 1 == 0, we can remove one digits among {1, 4, 7} => sum % 3 == 0
if sum % 2 == 0, we can remove one digits among {2, 5, 8} => sum % 3 == 0
if sum % 2 == 0, we have to remove two digits among {1, 4, 7} => sum % 3 == 0
if sum % 1 == 0, we have to remove two digits among {2, 5, 8} => sum % 3 == 0

Time complexity: O(n)
Space complexity: O(n) w/ output, O(1) w/o output

## Python3

If you like my articles / videos, donations are welcome.

Buy anything from Amazon to support our website

Paypal
Venmo
huahualeetcode

## Be First to Comment

Mission News Theme by Compete Themes.