Leetcode: 1363. Largest Multiple of Three

Can we simplify the problem while keeping it the same? As \(10^k \mod 3 = 1\), we are concerned on picking digits where their sum in divisible by \(3\). All digits divisible by \(3\) will be part of the answer, so the problem is to maximize \(2 \times x + y\) where \(x\) and \(y\) are the number of digits with rest \(2\) and \(1\) respectively. Time complexity is \(O(x \times y + n)\) and space is \(O(n)\).

from typing import List


class Solution:
    def largestMultipleOfThree(self, digits: List[int]) -> str:
        digits.sort(reverse=True)
        cmod = Counter([d % 3 for d in digits])
        r2 = r1 = 0
        for i in range(cmod[2] + 1):
            for j in range(cmod[1], -1, -1):
                if i + j < r2 + r1:
                    break
                if (2 * i + j) % 3 == 0:
                    r2 = i
                    r1 = j
        ans = deque()
        for d in digits:
            if d % 3 == 0:
                ans.append(d)
            if d % 3 == 1 and r1 > 0:
                r1 -= 1
                ans.append(d)
            if d % 3 == 2 and r2 > 0:
                r2 -= 1
                ans.append(d)
        while len(ans) > 1 and ans[0] == 0:
            ans.popleft()

        return "".join(map(str, ans))


assert Solution().largestMultipleOfThree([8, 1, 9]) == "981"
assert Solution().largestMultipleOfThree([8, 6, 7, 1, 0]) == "8760"
assert Solution().largestMultipleOfThree([1]) == ""