1363. Largest Multiple of Three


Problem Description

The problem requires creating the largest possible multiple of three from a given array of single-digit numbers (digits). The solution must concatenate elements from the array in any order to form the largest multiple of three. If it's not possible to form such a number, the solution should return an empty string. When forming the number, leading zeros should be discarded unless the number itself is zero. Since the expected output can be very large, the answer is required to be returned as a string.

Intuition

To solve this problem, we have to understand a few properties of multiples of three:

  1. Divisibility Rule for Three: For a number to be divisible by three, the sum of its digits must also be divisible by three.
  2. No Leading Zeros: Without loss of generality, we can ignore zeros at the beginning as they do not contribute to the value of the number. However, we must be careful to leave one zero if all digits are zeros.

Given these two points, we can outline the solution approach:

  1. Sorting: First, sort the array to make sure we can form the largest possible number at the end by concatenating the digits in descending order.
  2. Dynamic Programming (DP): Use DP to find the largest number we can make that is divisible by three. Create an array f where f[i][j] represents the maximum length of a subsequence formed by the first i digits that has a remainder of j when divided by 3.
  3. Subsequence Selection: Once the DP matrix is filled, reconstruct the largest possible number from it. We do this in two steps:
    • Start from f[n][0] (since this is where the subsequence with a sum divisible by three and the largest size will be stored) and trace back to find which digits are included in this subsequence.
    • Remove leading zeros, because they don't count unless the number is entirely composed of zeros.

This approach ensures that we'll find the largest subsequence of digits that satisfies the divisibility rule, and by sorting initially, we ensure it's the largest multiple of three possible with the given digits.

Learn more about Greedy and Dynamic Programming patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Solution Approach

The solution adopts a dynamic programming approach to construct the largest multiple of three from the array of digits. Let's break down the implementation:

  1. Sorting: digits.sort() is used to sort the array in ascending order so that when we construct our number, it is automatically arranged in descending order (as we will construct it backward).

  2. Dynamic Programming Initialization: Initialize a DP matrix f with dimensions (n + 1) x 3, where n is the number of digits. Each cell is initially filled with -inf to signify that there is no valid subsequence yet found for that combination.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which two pointer technique does Quick Sort use?

Example Walkthrough

Let's illustrate the solution approach with a small example.

Suppose we are given the array of digits [8, 1, 9, 3, 4, 5]. Our goal is to find the largest possible multiple of three.

  1. Sorting: We sort the array in ascending order, which gives us [1, 3, 4, 5, 8, 9].

  2. Dynamic Programming Initialization: Let n be the number of digits in the sorted array. We initialize a DP matrix f with dimensions (n + 1) x 3, which in our case is a 7x3 matrix since there are 6 digits. Each cell in f is initially filled with -inf, which represents that we haven't found any valid subsequences for that remainder. The first row of the DP matrix is initialized to 0, because a subsequence with 0 digits always has a remainder of 0 and a size of 0.

Now, we traverse the sorted array and update the DP matrix:

  • For the first digit, 1, we can only form numbers with a remainder of 1 (since 1 is not divisible by 3). We update f[1][1] with the length of this subsequence, which is 1 (just the single digit 1).
  • For the second digit, 3, which is divisible by three, we update f[2][0], f[2][1], and f[2][2] based on the previous results in f[1][0], f[1][1], and f[1][2] respectively. Since 3 adds a remainder of 0 to whatever we have, all remainders are possible.

This process continues until we've traversed all digits. For ease of illustration, let's assume the final updated DP matrix indicates the largest size subsequences ending in a remainder of 0, 1, or 2 modulo 3 are of sizes 5, inf, and inf, respectively.

  1. Subsequence Selection: Since we're interested in a multiple of three, we look at f[n][0]. Here, n is the total number of digits we started with, so we look at f[6][0]. Suppose f[6][0] indicates a size of 4. We then trace back through the DP matrix to determine which digits contribute to this subsequence of size 4 that sums to a multiple of three. Tracing backwards, let's say we identify the subsequence [9, 3, 5, 1].

Finally, since we require the largest possible number and we initially sorted the array in ascending order, we construct our number in reverse order. The largest possible multiple of three that we can obtain from the subsequence [9, 3, 5, 1] is 9531. Since there are no leading zeros to remove, this is our final answer.

The dynamic programming approach ensures that we have considered all possible combinations, and by reconstructing the sequence from the DP matrix, we get the largest value possible. Therefore, the largest multiple of three that we can form from the array [8, 1, 9, 3, 4, 5] is 9531.

Not Sure What to Study? Take the 2-min Quiz:

Which algorithm should you use to find a node that is close to the root of the tree?

Python Solution

1from math import inf
2from typing import List
3
4class Solution:
5    def largestMultipleOfThree(self, digits: List[int]) -> str:
6        # Sort the digits array in ascending order
7        digits.sort()
8        # Number of digits
9        n = len(digits)
10        # A 2D array to keep track of maximum length of subsequence that gives remainder j when divided by 3
11        dp = [[-inf for _ in range(3)] for _ in range(n + 1)]
12        # Initialize the subsequence length to 0 when there are no digits
13        dp[0][0] = 0
14      
15        # Dynamic programming to fill the 2D array
16        for i, digit in enumerate(digits, 1):
17            for remainder in range(3):
18                # Compare and select the maximum length between not picking and picking the digit
19                dp[i][remainder] = max(dp[i - 1][remainder],
20                                       dp[i - 1][(remainder - digit % 3 + 3) % 3] + 1)
21      
22        # If there is no subsequence which forms a multiple of three, return an empty string
23        if dp[n][0] <= 0:
24            return ""
25      
26        # Build the multiple of three by going backwards in the filled 2D array
27        subsequence = []
28        remainder = 0
29        for i in range(n, 0, -1):
30            next_remainder = (remainder - digits[i - 1] % 3 + 3) % 3
31            if dp[i - 1][next_remainder] + 1 == dp[i][remainder]:
32                # If the digit should be included, add to subsequence
33                subsequence.append(digits[i - 1])
34                remainder = next_remainder
35      
36        # Remove leading zeros
37        leading_zeros_removed = 0
38        while leading_zeros_removed < len(subsequence) - 1 and subsequence[leading_zeros_removed] == 0:
39            leading_zeros_removed += 1
40        # Concatenate the digits to form the required number
41        return "".join(map(str, subsequence[leading_zeros_removed:]))
42
43
44# Example usage:
45# solution = Solution()
46# print(solution.largestMultipleOfThree([8, 1, 9]))  # Output: "981"
47

Java Solution

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

C++ Solution

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

Typescript Solution

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
Fast Track Your Learning with Our Quick Skills Quiz:

Which two pointer technique does Quick Sort use?

Time and Space Complexity

The given code block is designed to find the largest number that can be formed from a list of digits such that the final number is a multiple of three.

Time Complexity:

The time complexity of the given solution can be analyzed as follows:

  • Initializing the list f with size (n + 1) * 3 takes O(n) time.
  • The outer loop runs n times, where n is the number of digits.
  • The inner loop runs a constant number of times (exactly 3 times) for each iteration of the outer loop.
  • Inside the inner loop, it computes the maximum of two values, which takes constant time O(1).
  • After the loops, it iterates from n down to 1 to construct the final result, which takes O(n) in the worst case.
  • Inside this iteration, there's a while loop that potentially iterates over all digits to skip leading zeros. In the worst case, it could iterate over all the elements, but this doesn't affect the overall time complexity.

Given the two main loops nested, with the outer loop running n times and the inner loop a constant 3 times, the overall time complexity is:

O(n) + O(n) * O(3) + O(n) = O(n)

Space Complexity:

The space complexity of the code can be analyzed as follows:

  • The f list is a 2D list with dimensions (n + 1) * 3, resulting in a space complexity of O(n).
  • The arr list can potentially contain every digit from the input in the worst case, thus has a space complexity of O(n).
  • Minimal extra space is utilized for variables such as i, j, k, and x, but this doesn't affect the overall space complexity.

Therefore, the total space complexity of the algorithm is:

O(n) + O(n) = O(n)

So the final space complexity is O(n).

Learn more about how to find time and space complexity quickly.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫