How do you solve Largest Multiple of Three on LeetCode?

Largest Multiple of Three (LeetCode #1363) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: A number is a multiple of three if the sum of its digits is a multiple of three.

What is the brute force solution for Largest Multiple of Three?

The brute force approach for Largest Multiple of Three is Brute Force, with O(n!) time complexity and O(n) space complexity. The brute force approach involves generating all possible combinations of the digits and checking which combinations form the largest number that is a multiple of three. This is straightforward but inefficient for larger inputs. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Largest Multiple of Three?

Largest Multiple of Three uses the following concepts: Array, Math, Dynamic Programming, Greedy, Sorting. The recommended patterns to study are: Greedy, Sorting.

What are the interview tips for Largest Multiple of Three?

Always clarify the problem constraints and edge cases. Think about the properties of numbers, like divisibility rules. Practice explaining your thought process clearly and logically.

What are common mistakes when solving Largest Multiple of Three?

Not considering leading zeros when constructing the final number. Failing to check the conditions for removing digits based on their remainders.

#1363

Largest Multiple of Three

Hard

ArrayMathDynamic ProgrammingGreedySortingGreedySorting

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n!)	O(n)
Space	O(n)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal approach leverages the properties of numbers and their divisibility by three. By counting the occurrences of each digit and strategically removing the smallest digits, we can efficiently construct the largest number that is a multiple of three.

⚙️

Algorithm

5 steps

1Step 1: Count the occurrences of each digit from 0 to 9.
2Step 2: Calculate the total sum of the digits and determine its remainder when divided by 3.
3Step 3: If the remainder is 1, try to remove the smallest digit with remainder 1 or two digits with remainder 2 to make the sum a multiple of three.
4Step 4: If the remainder is 2, try to remove the smallest digit with remainder 2 or two digits with remainder 1.
5Step 5: Construct the largest number from the remaining digits, ensuring no leading zeros.

solution.py30 lines

1def largestMultipleOfThree(digits):
2    count = [0] * 10
3    for d in digits:
4        count[d] += 1
5    total_sum = sum(digits)
6    remainder = total_sum % 3
7    if remainder == 1:
8        for i in range(1, 10):
9            if i % 3 == 1 and count[i] > 0:
10                count[i] -= 1
11                break
12        else:
13            for _ in range(2):
14                for i in range(1, 10):
15                    if i % 3 == 2 and count[i] > 0:
16                        count[i] -= 1
17                        break
18    elif remainder == 2:
19        for i in range(1, 10):
20            if i % 3 == 2 and count[i] > 0:
21                count[i] -= 1
22                break
23        else:
24            for _ in range(2):
25                for i in range(1, 10):
26                    if i % 3 == 1 and count[i] > 0:
27                        count[i] -= 1
28                        break
29    result = ''.join(str(i) * count[i] for i in range(9, -1, -1))
30    return result.lstrip('0') or ''

ℹ

Complexity note: The time complexity is O(n) because we only traverse the digits a few times. The space complexity is O(1) since we only use a fixed-size array for counting digits.

1A number is a multiple of three if the sum of its digits is a multiple of three.
2To maximize the number, sort the digits in descending order.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.