We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Largest Multiple of Three

Difficulty: Hard

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. If there is no answer return an empty string. The answer must not contain unnecessary leading zeros.

Key Insights

  • A number is a multiple of three if the sum of its digits is a multiple of three.
  • We can sort the digits in descending order to maximize the number formed.
  • Depending on the sum of the digits modulo 3, we may need to remove certain digits to achieve a sum that is a multiple of three.
  • Leading zeros must be handled to ensure the result is valid.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the digits.
Space Complexity: O(n) for storing the sorted digits.

Solution

To solve the problem, we can follow these steps:

  1. Calculate the sum of all digits.
  2. Sort the digits in descending order to form the largest possible number.
  3. Check the sum modulo 3:
    • If the sum is 0, the number is already valid.
    • If the sum is 1, try to remove one digit with a remainder of 1 when divided by 3, or remove two digits with a remainder of 2.
    • If the sum is 2, try to remove one digit with a remainder of 2, or remove two digits with a remainder of 1.
  4. After modifications, check for leading zeros and return the final result.

The data structure used is an array to hold the digits, and we utilize sorting and basic arithmetic for the algorithmic approach.

Code Solutions

def largestMultipleOfThree(digits):
    digits.sort(reverse=True)
    total_sum = sum(digits)
    
    if total_sum % 3 == 0:
        return ''.join(map(str, digits)) if digits[0] != 0 else '0'
    
    mod_count = [0, 0, 0]
    for d in digits:
        mod_count[d % 3] += 1
    
    if total_sum % 3 == 1:
        if mod_count[1] > 0:
            for d in digits:
                if d % 3 == 1:
                    digits.remove(d)
                    break
        else:
            for _ in range(2):
                for d in digits:
                    if d % 3 == 2:
                        digits.remove(d)
                        break
    
    elif total_sum % 3 == 2:
        if mod_count[2] > 0:
            for d in digits:
                if d % 3 == 2:
                    digits.remove(d)
                    break
        else:
            for _ in range(2):
                for d in digits:
                    if d % 3 == 1:
                        digits.remove(d)
                        break
    
    if not digits:
        return ''
    
    digits.sort(reverse=True)
    return ''.join(map(str, digits)) if digits[0] != 0 else '0'
← Back to All Questions