1363. Largest Multiple of Three 最大三的倍數

 1363. Largest Multiple of Three 最大三的倍數

這題與其說是程式 不如說是數論

首先把mod0, mod1, mod2的三個都分開 並且排序

如果數字總和是三的倍數 那就happy 排序以後組成的必定最大 因為位數最多

如果數字總和mod3=1 那就砍掉一個mod3=1的元素 必須是最小的 有1先砍,在4, or 7

如果不行 只好砍掉兩個mod 2的元素 

反過來說

如果數字總和mod3=2 那就砍掉一個mod3=2的元素 必須是最小的 有2先砍,在5, or 8

如果不行 只好砍掉兩個mod 1的元素

簡單數論可以證明，上述必有一種情況成立，即可

歡迎參考下面code 

class Solution:
    # give string from list
    def form_string(self,s):
        if s==[]: return ""
        s=sorted(s)[::-1]
        ans=""
        for i in s:
            ans+=str(i)
        
        # 0000 case 
        if ans.count("0")==len(ans):
            return "0"
        else:
            return ans
    
    def largestMultipleOfThree(self, digits: List[int]) -> str:
        
        a0,a1,a2=[],[],[]
        for i in digits:
            if i%3==0:
                a0.append(i)
            elif i%3==1:
                a1.append(i)
            else: 
                a2.append(i)
        a0=sorted(a0)[::-1]
        a1=sorted(a1)[::-1]
        a2=sorted(a2)[::-1]
        #print(a0,a1,a2)
        if sum(digits)%3==0:
            return self.form_string(digits)
        elif sum(digits)%3==1:
            if len(a1)>=1:
                return self.form_string(a0+a2+a1[:-1])
            return self.form_string(a0+a2[:-2]+a1)
        elif sum(digits)%3==2:
            if len(a2)>=1:
                return self.form_string(a0+a2[:-1]+a1)
            return self.form_string(a0+a2+a1[:-2])