LeetCode Solutions Blog

Largest Multiple of Three

Number: 1277

Difficulty: Hard

Paid? No

Problem Description

Given an array of digits, return the largest multiple of three that can be formed by concatenating some of the given digits in any order. The answer is returned as a string and must not contain unnecessary leading zeros. If no valid number exists, return an empty string.

Key Insights

A number is divisible by 3 if the sum of its digits is divisible by 3.
Sorting digits in descending order produces the largest possible number.
If the total sum of digits is not divisible by 3, remove the smallest digit(s) with the required remainder.
- For a remainder of 1: remove one digit with remainder 1, or two digits with remainder 2.
- For a remainder of 2: remove one digit with remainder 2, or two digits with remainder 1.
Special care is needed to handle cases where the result might be all zeros.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting, where n is the number of digits.
Space Complexity: O(n) for storing digits in buckets and the result list.

Solution

The solution begins by calculating the total sum of the digits. Depending on the remainder (when dividing by 3), we decide which digits to remove:

If the sum is already divisible by 3, sort all digits in descending order to form the answer.
If the remainder is 1 or 2, attempt to remove the smallest digit (or two) that will cancel out the remainder.
Finally, combine all the remaining digits, sort them in descending order to maximize the number, and construct the result string. Special handling ensures that if the result starts with zero (i.e., all digits are 0) it returns "0".

Code Solutions

Below are code solutions in Python, JavaScript, C++, and Java with line-by-line comments.

# Function to compute the largest multiple of three from given digits.
def largestMultipleOfThree(digits):
    # Calculate the total sum of digits.
    total_sum = sum(digits)
    # Create remainder buckets for digits.
    remainder_buckets = {0: [], 1: [], 2: []}
    for digit in digits:
        remainder_buckets[digit % 3].append(digit)
    # Sort each bucket in ascending order for minimal removal.
    for rem in remainder_buckets:
        remainder_buckets[rem].sort()
    
    remainder = total_sum % 3
    # Adjust the buckets based on the remainder.
    if remainder == 1:
        if remainder_buckets[1]:
            # Remove the smallest digit with remainder 1.
            remainder_buckets[1].pop(0)
        elif len(remainder_buckets[2]) >= 2:
            # Remove two smallest digits with remainder 2.
            remainder_buckets[2].pop(0)
            remainder_buckets[2].pop(0)
        else:
            return ""
    elif remainder == 2:
        if remainder_buckets[2]:
            # Remove the smallest digit with remainder 2.
            remainder_buckets[2].pop(0)
        elif len(remainder_buckets[1]) >= 2:
            # Remove two smallest digits with remainder 1.
            remainder_buckets[1].pop(0)
            remainder_buckets[1].pop(0)
        else:
            return ""
    
    # Combine remaining digits from all buckets.
    result_digits = remainder_buckets[0] + remainder_buckets[1] + remainder_buckets[2]
    if not result_digits:
        return ""
    # Sort the digits in descending order to form the maximum number.
    result_digits.sort(reverse=True)
    result = "".join(map(str, result_digits))
    # Check for case where the highest digit is '0'
    if result[0] == "0":
        return "0"
    return result

# Example usage:
print(largestMultipleOfThree([8, 1, 9]))  # Expected output: "981"