Leetcode 1363. Largest Multiple of Three

Problem statement

https://leetcode.com/problems/largest-multiple-of-three/

Solution

We need to property of divisibility by 3. If sum of all digits divisible by 3, do nothing. If it is 1, we need to remove either one digit if possible or 2 digits. If it is 2, logic is similar. Then we need to reconstruct number.

Complexity

Time complexity is O(n*log n), because we do sorts. In fact we can avoid this, if we use bucket sort and make it in O(n), but the speed will be almost the same, because sort works very fast.

Code

class Solution:
    def largestMultipleOfThree(self, digits):
        mod = sum(digits) % 3
        mods = [[],[],[]]
        for d in digits: mods[d%3].append(d)  
        for i in range(3): mods[i] = sorted(mods[i])[::-1]
            
        if mod != 0:
            if len(mods[mod]) >= 1: 
                mods[mod].pop()
            else:
                mods[3-mod].pop()
                mods[3-mod].pop()
                
        t = "".join(str(i) for i in sorted(mods[0] + mods[1] + mods[2])[::-1])
        return t if not t else str(int(t))