Q1363. Largest Multiple of Three

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.

At the beginning, it is easy to get the idea that this problem should be solved by dynamic programming. And the answer will be constantly built upon previous problem.

The key observation is that the number that divides 3 have all digits summation dividing 3. So, we can easily build the current solution from the max number with sum modulo 3 equals k (k = 0, 1, 2). Let the dp[k] indicate the solution with digits sum modulo 3 equals k. For the ith number, the update rule for dp[k] is:

• Compare dp[k] and dp[ (k - digits[i]) % 3 ] with digits[i] being added.

We should update dp[k] to the one that gives rise to a bigger number.

OK, here comes to the real tricky part. For me, I did not get the right data structure to use to make this comparison efficient enough (we need to do it in $O(1)$).

I was thinking about a sorted list, which is hard to update and maintain. It turns out that we should use an 10-element array with each element representing the count of one digits.

The Python submission is as follow.

class Solution:
    def largestMultipleOfThree(self, digits: List[int]) -> str:
        if len(digits) == 0:
            return ''
        soln = [ [ 0 for i in range(10) ] for j in range(3) ]
        for d in digits:
            new_soln = [ [] for j in range(3) ]
            for i in range(3):
                j = (d + i) % 3
                tmp = [ 0 for i_ in range(10) ]
                if sum(soln[i]) > 0 or i == 0:
                    tmp = soln[i][:]
                    tmp[d] += 1
                if sum(tmp) > sum(soln[j]) or (sum(tmp) == sum(soln[j]) and tmp[::-1] > soln[j][::-1]):
                    new_soln[j] = tmp
                else: 
                    new_soln[j] = soln[j]
            soln = new_soln
            # print(soln)
        if sum(soln[0]) == 0:
            return ''
        tmp = [ str(i) * n for i, n in enumerate(soln[0]) ]
        res = ''.join([ t for t in reversed(tmp) ])
        if res[0] == '0':
            return '0'
        return res