# 1363. Largest Multiple of Three

• Time:
• Space:
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 class Solution { public: string largestMultipleOfThree(vector& digits) { string ans; vector mod1{1, 4, 7, 2, 5, 8}; vector mod2{2, 5, 8, 1, 4, 7}; vector count(10); int sum = accumulate(digits.begin(), digits.end(), 0); for (const int digit : digits) ++count[digit]; while (sum % 3 != 0) for (int i : sum % 3 == 1 ? mod1 : mod2) if (count[i]) { --count[i]; sum -= i; break; } for (int digit = 9; digit >= 0; --digit) ans += string(count[digit], '0' + digit); return ans.size() && ans[0] == '0' ? "0" : ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class Solution { public String largestMultipleOfThree(int[] digits) { StringBuilder ans = new StringBuilder(); int[] mod1 = new int[] {1, 4, 7, 2, 5, 8}; int[] mod2 = new int[] {2, 5, 8, 1, 4, 7}; int[] count = new int[10]; int sum = 0; for (int digit : digits) { ++count[digit]; sum += digit; } while (sum % 3 != 0) for (int i : sum % 3 == 1 ? mod1 : mod2) if (count[i] > 0) { --count[i]; sum -= i; break; } for (int digit = 9; digit >= 0; --digit) ans.append(Character.toString('0' + digit).repeat(count[digit])); return ans.length() > 0 && ans.charAt(0) == '0' ? "0" : ans.toString(); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution: def largestMultipleOfThree(self, digits: List[int]) -> str: ans = '' mod1 = [1, 4, 7, 2, 5, 8] mod2 = [2, 5, 8, 1, 4, 7] count = collections.Counter(digits) summ = sum(digits) while summ % 3 != 0: for digit in (mod1 if summ % 3 == 1 else mod2): if count[digit]: count[digit] -= 1 summ -= digit break for digit in reversed(range(10)): ans += str(digit) * count[digit] return '0' if len(ans) and ans[0] == '0' else ans