1363. Largest Multiple of Three

1import java.util.Arrays;
2
3class Solution {
4    public String largestMultipleOfThree(int[] digits) {
5        // Sort the array in ascending order
6        Arrays.sort(digits);
7
8        // Get the length of the digits array
9        int length = digits.length;
10
11        // Initialize a 2D dynamic programming array to store the maximum count of digits that can form a multiple of three
12        int[][] dp = new int[length + 1][3];
13
14        // Define an 'inf' (infinity) value as a very large number to be used in our calculations
15        final int INF = Integer.MAX_VALUE / 2; // Using half of MAX_VALUE to avoid overflow
16
17        // Fill the dynamic programming array with negative infinity to differentiate between used and unused states
18        for (int[] row : dp) {
19            Arrays.fill(row, -INF);
20        }
21
22        // The count for zero elements to form a sum that is a multiple of three is zero
23        dp[0][0] = 0;
24
25        // Build the dynamic programming matrix
26        for (int i = 1; i <= length; ++i) {
27            for (int j = 0; j < 3; ++j) {
28                // Get the mod value of the current digit
29                int modValue = (j - digits[i - 1] % 3 + 3) % 3;
30
31                // Maximize the count for dp[i][j] by either taking the previous count or by including the current digit if it can contribute
32                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][modValue] + 1);
33            }
34        }
35
36        // If there is no combination that forms a multiple of three, return an empty string
37        if (dp[length][0] <= 0) {
38            return "";
39        }
40
41        // Use StringBuilder to construct the largest number that is a multiple of three
42        StringBuilder resultBuilder = new StringBuilder();
43
44        // Trace back the dynamic programming table in reverse to build the number
45        for (int i = length, j = 0; i > 0; --i) {
46            // Calculate the previous mod value to decide if the current digit should be included
47            int previousMod = (j - digits[i - 1] % 3 + 3) % 3;
48
49            // If including the current digit leads to the maximum count, append it to the resultBuilder
50            // and update the mod value
51            if (dp[i - 1][previousMod] + 1 == dp[i][j]) {
52                resultBuilder.append(digits[i - 1]);
53                j = previousMod;
54            }
55        }
56
57        // Remove leading zeros if any
58        int startIndex = 0;
59        while (startIndex < resultBuilder.length() - 1 && resultBuilder.charAt(startIndex) == '0') {
60            ++startIndex;
61        }
62
63        // Return the final result string starting from the first non-zero digit
64        return resultBuilder.substring(startIndex);
65    }
66}
67

1#include <vector>
2#include <string>
3#include <algorithm>
4#include <cstring>
5
6class Solution {
7public:
8    // Function that finds the largest multiple of three using the given digits.
9    std::string largestMultipleOfThree(std::vector<int>& digits) {
10        // Sort the digits in non-decreasing order
11        std::sort(digits.begin(), digits.end());
12        int numDigits = digits.size();
13      
14        // Initializing the dynamic programming table with a very negative number
15        int dp[numDigits + 1][3];
16        memset(dp, -0x3f, sizeof(dp));
17      
18        // Base case: for 0 digits, the sum = 0 mod 3 is achievable with count 0
19        dp[0][0] = 0;
20      
21        // Build the table in bottom-up manner
22        for (int i = 1; i <= numDigits; ++i) {
23            for (int j = 0; j < 3; ++j) {
24                int prevMod = (j - digits[i - 1] % 3 + 3) % 3;
25                // Pick the larger of not taking the current digit or taking it
26                dp[i][j] = std::max(dp[i - 1][j], dp[i - 1][prevMod] + 1);
27            }
28        }
29      
30        // If there's no solution (sum = 0 mod 3 not reachable), return an empty string
31        if (dp[numDigits][0] <= 0) {
32            return "";
33        }
34      
35        std::string result;
36        int mod = 0; // The current remainder
37      
38        // Construct the result string by choosing digits in reverse order
39        for (int i = numDigits; i > 0; --i) {
40            int modToCheck = (mod - digits[i - 1] % 3 + 3) % 3;
41            if (dp[i - 1][modToCheck] + 1 == dp[i][mod]) {
42                result += (char)('0' + digits[i - 1]);
43                mod = modToCheck;
44            }
45        }
46      
47        // Remove leading zeros except the last zero if the result is zero
48        int startNonZero = 0;
49        while (startNonZero < result.size() - 1 && result[startNonZero] == '0') {
50            ++startNonZero;
51        }
52      
53        // Get the substring from the first non-zero character
54        return result.substr(startNonZero);
55    }
56};
57

1function largestMultipleOfThree(digits: number[]): string {
2    // Sort the digits array in non-decreasing order.
3    digits.sort((a, b) => a - b);
4
5    // Get the number of digits.
6    const numDigits = digits.length;
7
8    // f array for dynamic programming, where f[i][j] will store the maximum length
9    // of a subsequence of the first i digits with a sum modulo 3 equal to j.
10    const dpArray: number[][] = new Array(numDigits + 1).fill(0).map(() => new Array(3).fill(-Infinity));
11    dpArray[0][0] = 0;
12
13    // Dynamic programming to fill the dpArray.
14    for (let i = 1; i <= numDigits; ++i) {
15        for (let j = 0; j < 3; ++j) {
16            const mod = (j - digits[i - 1] % 3 + 3) % 3;
17            dpArray[i][j] = Math.max(dpArray[i - 1][j], dpArray[i - 1][mod] + 1);
18        }
19    }
20
21    // If there are no subsequences whose sum is divisible by 3, return an empty string.
22    if (dpArray[numDigits][0] <= 0) {
23        return '';
24    }
25
26    // Iterate backwards to find the digits that make up the largest multiple of three.
27    const resultDigits: number[] = [];
28    for (let i = numDigits, sumModulo = 0; i > 0; --i) {
29        const currentDigitModulo = (sumModulo - digits[i - 1] % 3 + 3) % 3;
30      
31        // If including the current digit gives us a longer subsequence.
32        if (dpArray[i - 1][currentDigitModulo] + 1 === dpArray[i][sumModulo]) {
33            resultDigits.push(digits[i - 1]); // Add digit to the result.
34            sumModulo = currentDigitModulo;   // Update the sum modulo for previous digits.
35        }
36    }
37
38    // Remove any leading zeros except for the last digit if the number is zero.
39    let leadingZeroIndex = 0;
40    while (leadingZeroIndex < resultDigits.length - 1 && resultDigits[leadingZeroIndex] === 0) {
41        ++leadingZeroIndex;
42    }
43
44    // Join the result digits to form the largest multiple of three and return it as a string.
45    return resultDigits.slice(leadingZeroIndex).reverse().join('');
46}
47