Skip to content

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<int>& digits) {
    string ans;
    vector<int> mod1{1, 4, 7, 2, 5, 8};
    vector<int> mod2{2, 5, 8, 1, 4, 7};
    vector<int> 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