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:
- Divisibility Rule for Three: For a number to be divisible by three, the sum of its digits must also be divisible by three.
- 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:
- 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.
- Dynamic Programming (DP): Use DP to find the largest number we can make that is divisible by three. Create an array
f
wheref[i][j]
represents the maximum length of a subsequence formed by the firsti
digits that has a remainder ofj
when divided by 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.
- Start from
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.
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:
-
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). -
Dynamic Programming Initialization: Initialize a DP matrix
f
with dimensions(n + 1) x 3
, wheren
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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.
-
Sorting: We sort the array in ascending order, which gives us
[1, 3, 4, 5, 8, 9]
. -
Dynamic Programming Initialization: Let
n
be the number of digits in the sorted array. We initialize a DP matrixf
with dimensions(n + 1) x 3
, which in our case is a 7x3 matrix since there are 6 digits. Each cell inf
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 to0
, because a subsequence with0
digits always has a remainder of0
and a size of0
.
Now, we traverse the sorted array and update the DP matrix:
- For the first digit,
1
, we can only form numbers with a remainder of1
(since 1 is not divisible by 3). We updatef[1][1]
with the length of this subsequence, which is1
(just the single digit1
). - For the second digit,
3
, which is divisible by three, we updatef[2][0]
,f[2][1]
, andf[2][2]
based on the previous results inf[1][0]
,f[1][1]
, andf[1][2]
respectively. Since3
adds a remainder of0
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.
- 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 atf[6][0]
. Supposef[6][0]
indicates a size of4
. We then trace back through the DP matrix to determine which digits contribute to this subsequence of size4
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
.
Solution Implementation
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
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
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
takesO(n)
time. - The outer loop runs
n
times, wheren
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 to1
to construct the final result, which takesO(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 ofO(n)
. - The
arr
list can potentially contain every digit from the input in the worst case, thus has a space complexity ofO(n)
. - Minimal extra space is utilized for variables such as
i
,j
,k
, andx
, 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 using problem constraints.
How does merge sort divide the problem into subproblems?
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we