Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1363.html
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^40 <= 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.
- Removing a digit from
- If
total % 3 == 2, we have two options:- Removing a digit from
2, 5, 8. - Removing two digits from
1, 4, 7.
- Removing a digit from
- If after all these operations, the
totalis still not divisible by3, then we need to remove all1, 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/
// 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/
// 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;
}
};
-
class Solution { public String largestMultipleOfThree(int[] digits) { Arrays.sort(digits); List<Integer> remainderZeros = new ArrayList<Integer>(); List<Integer> remainderOnes = new ArrayList<Integer>(); List<Integer> remainderTwos = new ArrayList<Integer>(); int sum = 0; int length = digits.length; for (int i = 0; i < length; i++) { int digit = digits[i]; sum += digit; if (digit % 3 == 0) remainderZeros.add(digit); else if (digit % 3 == 1) remainderOnes.add(digit); else remainderTwos.add(digit); } int remainder = sum % 3; if (remainder == 0) { StringBuffer sb = new StringBuffer(); for (int i = 0; i < length; i++) sb.append(digits[i]); sb.reverse(); if (sb.charAt(0) == '0') return "0"; else return sb.toString(); } else if (remainder == 1) { if (remainderOnes.size() >= 1) { int minOne = remainderOnes.get(0); boolean flag = false; StringBuffer sb = new StringBuffer(); for (int i = 0; i < length; i++) { int digit = digits[i]; if (!flag) { if (digit == minOne) flag = true; else sb.append(digit); } else sb.append(digit); } sb.reverse(); if (sb.length() == 0) return ""; else if (sb.charAt(0) == '0') return "0"; else return sb.toString(); } else if (remainderTwos.size() >= 2) { int minTwo1 = remainderTwos.get(0), minTwo2 = remainderTwos.get(1); int deleteCount = 0; StringBuffer sb = new StringBuffer(); for (int i = 0; i < length; i++) { int digit = digits[i]; if (deleteCount == 0) { if (digit == minTwo1) deleteCount++; else sb.append(digit); } else if (deleteCount == 1) { if (digit == minTwo2) deleteCount++; else sb.append(digit); } else sb.append(digit); } sb.reverse(); if (sb.length() == 0) return ""; else if (sb.charAt(0) == '0') return "0"; else return sb.toString(); } else return ""; } else { if (remainderTwos.size() >= 1) { int minTwo = remainderTwos.get(0); boolean flag = false; StringBuffer sb = new StringBuffer(); for (int i = 0; i < length; i++) { int digit = digits[i]; if (!flag) { if (digit == minTwo) flag = true; else sb.append(digit); } else sb.append(digit); } sb.reverse(); if (sb.length() == 0) return ""; else if (sb.charAt(0) == '0') return "0"; else return sb.toString(); } else if (remainderOnes.size() >= 2) { int minOne1 = remainderOnes.get(0), minOne2 = remainderOnes.get(1); int deleteCount = 0; StringBuffer sb = new StringBuffer(); for (int i = 0; i < length; i++) { int digit = digits[i]; if (deleteCount == 0) { if (digit == minOne1) deleteCount++; else sb.append(digit); } else if (deleteCount == 1) { if (digit == minOne2) deleteCount++; else sb.append(digit); } else sb.append(digit); } sb.reverse(); if (sb.length() == 0) return ""; else if (sb.charAt(0) == '0') return "0"; else return sb.toString(); } else return ""; } } } -
// OJ: https://leetcode.com/problems/largest-multiple-of-three/ // 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; } }; -
class Solution: def largestMultipleOfThree(self, digits: List[int]) -> str: digits.sort() n = len(digits) f = [[-inf] * 3 for _ in range(n + 1)] f[0][0] = 0 for i, x in enumerate(digits, 1): for j in range(3): f[i][j] = max(f[i - 1][j], f[i - 1][(j - x % 3 + 3) % 3] + 1) if f[n][0] <= 0: return "" arr = [] j = 0 for i in range(n, 0, -1): k = (j - digits[i - 1] % 3 + 3) % 3 if f[i - 1][k] + 1 == f[i][j]: arr.append(digits[i - 1]) j = k i = 0 while i < len(arr) - 1 and arr[i] == 0: i += 1 return "".join(map(str, arr[i:])) -
func largestMultipleOfThree(digits []int) string { sort.Ints(digits) n := len(digits) const inf = 1 << 30 f := make([][]int, n+1) for i := range f { f[i] = make([]int, 3) for j := range f[i] { f[i][j] = -inf } } f[0][0] = 0 for i := 1; i <= n; i++ { for j := 0; j < 3; j++ { f[i][j] = max(f[i-1][j], f[i-1][(j-digits[i-1]%3+3)%3]+1) } } if f[n][0] <= 0 { return "" } ans := []byte{} for i, j := n, 0; i > 0; i-- { k := (j - digits[i-1]%3 + 3) % 3 if f[i][j] == f[i-1][k]+1 { ans = append(ans, byte('0'+digits[i-1])) j = k } } i := 0 for i < len(ans)-1 && ans[i] == '0' { i++ } return string(ans[i:]) } func max(a, b int) int { if a > b { return a } return b } -
function largestMultipleOfThree(digits: number[]): string { digits.sort((a, b) => a - b); const n = digits.length; const f: number[][] = new Array(n + 1).fill(0).map(() => new Array(3).fill(-Infinity)); f[0][0] = 0; for (let i = 1; i <= n; ++i) { for (let j = 0; j < 3; ++j) { f[i][j] = Math.max(f[i - 1][j], f[i - 1][(j - (digits[i - 1] % 3) + 3) % 3] + 1); } } if (f[n][0] <= 0) { return ''; } const arr: number[] = []; for (let i = n, j = 0; i; --i) { const k = (j - (digits[i - 1] % 3) + 3) % 3; if (f[i - 1][k] + 1 === f[i][j]) { arr.push(digits[i - 1]); j = k; } } let i = 0; while (i < arr.length - 1 && arr[i] === 0) { ++i; } return arr.slice(i).join(''); }