1363. Largest Multiple of Three

1363. Largest Multiple of Three (Hard)

Given an integer array of digits, return the largest multiple of three that can be formed by concatenating some of the given digits in any order.

Since the answer may not fit in an integer data type, return the answer as a string.

If there is no answer return an empty string.

 

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: ""

Example 4:

Input: digits = [0,0,0,0,0,0]
Output: "0"

 

Constraints:

• 1 <= digits.length <= 10^4
• 0 <= digits[i] <= 9
• The returning answer must not contain unnecessary leading zeros.

Related Topics:
Math, Dynamic Programming

Solution 1.

We can safely add all 0, 3, 6, 9 digits.

For the rest 1, 2, 4, 5, 7, 8, can we add the digit 3 times if its count >= 3? No. The following is a counter example.

[2,2,1,1,1]   // 2211. Adding `1` 3 times first is not the optimal solution

[2,1,1,1]     // 111

In fact, n % 3 is the same as sum of all the digits in n modulo by 3.

999....999 % 3 == 0
1000....000 % 3 == 1
a000....000 % 3 == a % 3
abcdefghijk % 3 == (a+b+c+..+i+j+k) % 3

So assume total is the sum of all digits.

• If total % 3 == 0, we can add all digits.
• If total % 3 == 1, we have two options:
  • Removing a digit from 1, 4, 7.
  • Removing two digits from 2, 5, 8.
• If total % 3 == 2, we have two options:
  • Removing a digit from 2, 5, 8.
  • Removing two digits from 1, 4, 7.
• If after all these operations, the total is still not divisible by 3, then we need to remove all 1, 2, 4, 5, 7, 8.

Since we prefer removing as less digits as possible, we should always try removing one digit first.

// OJ: https://leetcode.com/problems/largest-multiple-of-three/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
// Ref: https://leetcode.com/problems/largest-multiple-of-three/discuss/517628/Python-Basic-Math
class Solution {
public:
    string largestMultipleOfThree(vector<int>& A) {
        int cnt[10] = {}, total = 0;
        for (int n : A) {
            cnt[n]++;
            total += n;
        }
        auto f = [&](int i) {
            if (cnt[i]) {
                cnt[i]--;
                total -= i;
            }
            return total % 3 == 0;
        };
        bool done = total % 3 == 0;
        if (!done) {
            if (total % 3 == 1) done = f(1) || f(4) || f(7) || f(2) || f(2) || f(5) || f(5) || f(8) || f(8);
            else done = f(2) || f(5) || f(8) || f(1) || f(1) || f(4) || f(4) || f(7) || f(7);
        }
        if (!done) cnt[1] = cnt[2] = cnt[4] = cnt[5] = cnt[7] = cnt[8] = 0;
        string ans;
        for (int i = 9; i >= 0; --i) {
            while (cnt[i]-- > 0) ans += '0' + i;
        }
        return ans[0] == '0' ? "0" : ans;
    }
};

Or

// OJ: https://leetcode.com/problems/largest-multiple-of-three/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    string largestMultipleOfThree(vector<int>& A) {
        int cnt[10] = {}, s = 0, nums[6] = {1,4,7,2,5,8};
        for (int n : A) cnt[n]++, s += n;
        if (s % 3 == 2 && cnt[2]) cnt[2]--, s -= 2;
        if (s % 3 == 2 && cnt[5]) cnt[5]--, s -= 5;
        if (s % 3 == 2 && cnt[8]) cnt[8]--, s -= 8;
        for (int n : nums) {
            while (s % 3 && cnt[n]) cnt[n]--, s -= n;
        }
        if (s == 0) return cnt[0] ? "0" : "";
        string ans;
        for (int i = 9; i >= 0; --i) {
            while (cnt[i]-- > 0) ans += '0' + i;
        }
        return ans;
    }
};