1363. Largest Multiple of Three LeetCode Solution

In this guide, you will get 1363. Largest Multiple of Three LeetCode Solution with the best time and space complexity. The solution to Largest Multiple of Three problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Largest Multiple of Three solution in C++
Largest Multiple of Three solution in Java
Largest Multiple of Three solution in Python
Additional Resources

1363. Largest Multiple of Three LeetCode Solution image

Problem Statement of Largest Multiple of Three

Given an array of digits digits, return the largest multiple of three that can be formed by concatenating some of the given digits in any order. If there is no answer return an empty string.
Since the answer may not fit in an integer data type, return the answer as a string. Note that the returning answer must not contain unnecessary leading zeros.

Example 1:

Input: digits = [8,1,9]
Output: “981”

Example 2:

Input: digits = [8,6,7,1,0]
Output: “8760”

Example 3:

Input: digits = [1]
Output: “”

Constraints:

1 <= digits.length <= 104
0 <= digits[i] <= 9

Complexity Analysis

Time Complexity:
Space Complexity:

1363. Largest Multiple of Three LeetCode Solution in C++

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;
  }
};
/* code provided by PROGIEZ */

1363. Largest Multiple of Three LeetCode Solution in Java

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();
  }
}
// code provided by PROGIEZ

1363. Largest Multiple of Three LeetCode Solution in Python

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
 # code by PROGIEZ