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^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/
// 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('');
    }
    
    

All Problems

All Solutions