Jobs

Interviews

Discussions

Largest Multiple of Three

Hard

Asked by:

43 views

Topics:

ArraysGreedy AlgorithmsStrings

Given an array of digits 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.

Since the answer may not fit in an integer data type, return the answer as a string. Note that the returning answer must not contain unnecessary leading zeros.

Example 1:

Input: digits = [8,1,9]
Output: "981"

Example 2:

Input: digits = [8,6,7,1,0]
Output: "8760"

Example 3:

Input: digits = [1]
Output: ""

Constraints:

1 <= digits.length <= 10⁴
0 <= digits[i] <= 9

Try coding it in LeetCode

Largest Multiple of Three

Hard

Asked by:

43 views

Topics:

ArraysGreedy AlgorithmsStrings

Since the answer may not fit in an integer data type, return the answer as a string. Note that the returning answer must not contain unnecessary leading zeros.

Example 1:

Input: digits = [8,1,9]
Output: "981"

Example 2:

Input: digits = [8,6,7,1,0]
Output: "8760"

Example 3:

Input: digits = [1]
Output: ""

Constraints:

1 <= digits.length <= 10⁴
0 <= digits[i] <= 9

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for each digit in the input array? Can the digits be negative?
What should I return if it's not possible to form a multiple of three with the given digits?
Are the digits provided as integers, or strings? And are they guaranteed to be single digits (0-9)?
If multiple largest multiples of three can be formed, is there any preference for which one to return (e.g., lexicographically largest)?
Does the order of digits in the input array matter? That is, do I need to maintain the relative ordering of the provided digits in the final result?

Brute Force Solution

Approach

The brute force method for finding the largest multiple of three from a set of digits involves considering every possible combination of digits. We essentially try building all possible numbers using different selections from the input digits. Then, we check each constructed number to see if it's divisible by three and keep track of the largest one we find.

Here's how the algorithm would work step-by-step:

Start by forming all possible numbers you can make using the given digits.
This includes single-digit numbers, two-digit numbers, three-digit numbers, and so on, up to using all the digits together.
For each of these numbers you created, check if it can be divided evenly by three (meaning, if you divide by three, there's no remainder).
If a number can be divided by three, compare it to the largest multiple of three you've found so far.
If the new number is bigger than the largest one you've seen, replace the largest one with this new number.
Continue until you've tried all possible number combinations.
The largest multiple of three you have at the end is the answer.

Code Implementation

def largest_multiple_of_three_brute_force(digits):
    largest_multiple = ""

    def generate_combinations(current_combination, remaining_digits):
        nonlocal largest_multiple

        # Convert the current combination to an integer and check divisibility.
        if current_combination:
            number = int("".join(map(str, sorted(current_combination, reverse=True))))
            if number % 3 == 0:
                if largest_multiple == "" or number > int(largest_multiple):
                    largest_multiple = str(number)

        # If we've run out of digits, stop.
        if not remaining_digits:
            return

        # Iterate through the remaining digits to build combinations.
        for i in range(len(remaining_digits)):
            # Recursively generate combinations by including each digit.
            generate_combinations(current_combination + [remaining_digits[i]], remaining_digits[:i] + remaining_digits[i+1:])

    generate_combinations([], digits)

    if largest_multiple == "":
        return ""

    # Handle leading zeros, like "000" should be "0".
    if all(digit == '0' for digit in largest_multiple):
        return "0"

    return largest_multiple

Big(O) Analysis

Time Complexity

O(2^n) – The brute force approach considers all possible subsets of the input digits. For an input array of size n, there are 2^n possible subsets (each digit can either be included or excluded). For each subset, we construct a number and check if it's divisible by 3. Therefore, the time complexity is dominated by the generation and checking of all these subsets, resulting in O(2^n) time complexity, where n is the number of digits in the input.

Space Complexity

O(2^N) – The brute force approach, as described, explores all possible combinations of digits from the input array of size N. This implicitly involves generating a power set, where each subset represents a potential number. The space required to store all these subsets could reach up to 2^N in the worst-case scenario as the algorithm keeps track of the generated numbers. Therefore, the space complexity grows exponentially with the size of the input array.

Optimal Solution

Approach

To find the largest multiple of three that can be formed from a set of digits, we focus on building the largest number possible and then adjusting to make it divisible by three. The core idea is to remove the smallest number of digits to achieve divisibility by three while keeping the remaining digits as large as possible.

Here's how the algorithm would work step-by-step:

First, add up all the digits to see if the original number (formed by arranging all the digits from largest to smallest) is already divisible by three. If so, you're done: sort the digits in descending order to get the biggest number and return it.
If the sum of the digits isn't divisible by three, find out the remainder when you divide the sum by three. This remainder tells us how much we need to reduce the sum by to make it divisible by three.
If the remainder is one, it means we need to remove one digit that leaves a remainder of one when divided by three, or remove two digits that each leave a remainder of two when divided by three. Pick the option that removes the smallest digits.
If the remainder is two, it means we need to remove one digit that leaves a remainder of two when divided by three, or remove two digits that each leave a remainder of one when divided by three. Pick the option that removes the smallest digits.
After removing the necessary digits, sort the remaining digits in descending order to form the largest possible number.
If all remaining digits are zero, the largest multiple of three is simply zero. If there are no remaining digits, return an empty string.
Construct the final string from the sorted digits, making sure to handle the case where the result is an empty string.

Code Implementation

def largestMultipleOfThree(digits):
    sum_of_digits = sum(digits)

    # If the sum is divisible by three, simply sort and return
    if sum_of_digits % 3 == 0:
        digits.sort(reverse=True)
        result = ''.join(map(str, digits))
        return '0' if result == '0' * len(result) else result

    remainder = sum_of_digits % 3

    # Function to remove digits based on remainder
    def remove_digits(remainder_to_remove):
        group_one = []
        group_two = []
        for digit in sorted(digits):
            if digit % 3 == 1:
                group_one.append(digit)
            elif digit % 3 == 2:
                group_two.append(digit)

        if remainder_to_remove == 1:
            if group_one:
                digits.remove(group_one[0])
                return True
            elif len(group_two) >= 2:
                digits.remove(group_two[0])
                digits.remove(group_two[1])
                return True
        else:
            if group_two:
                digits.remove(group_two[0])
                return True
            elif len(group_one) >= 2:
                digits.remove(group_one[0])
                digits.remove(group_one[1])
                return True
        return False

    # Remove the necessary digits
    if not remove_digits(remainder):
        return ''

    digits.sort(reverse=True)
    result = ''.join(map(str, digits))

    # Handle all zeros case
    if result == '0' * len(result):
        return '0'

    return result

Big(O) Analysis

Time Complexity

O(n log n) – The dominant operation is sorting the input array of n digits, which takes O(n log n) time. Calculating the sum of digits and determining the remainder when divided by 3 takes O(n) time. Finding and removing digits to make the sum divisible by 3 involves iterating through the array, which is also O(n). Re-sorting the remaining digits after removal again takes O(n log n) time. Therefore, the overall time complexity is O(n log n) + O(n) + O(n) + O(n log n), which simplifies to O(n log n).

Space Complexity

O(N) – The space complexity is primarily determined by the need to potentially store the digits in a sorted manner and create new lists by removing certain digits. Sorting the input digits requires O(N) space in the worst case. Additionally, if digits need to be removed to make the number divisible by three, we may create a modified list of digits which would take at most O(N) space. Therefore, the space complexity scales linearly with the number of digits N.

Edge Cases

Case	How to Handle
Empty input list	Return an empty string as there is no multiple of three that can be formed.
List contains only zeros	Return '0' as this is the largest multiple of three.
List contains digits that sum to a value not divisible by 3, but removing one or two smallest digits results in a divisible sum	Iteratively remove the smallest 1 or 2 digits that give remainder 1 or 2 mod 3.
List contains only digits that sum to a value not divisible by 3, and no removal of digits can make it divisible by 3.	Return an empty string since no multiple of 3 can be formed.
List contains a very large number of digits.	The solution should be designed to avoid integer overflow when calculating the sum and avoid creating too many copies of sublists.
Input list contains leading zeros after processing.	Remove leading zeros from the resulting string, unless the entire string becomes empty, in which case it should be '0'.
Input digits are already sorted in descending order.	The sorting step should not cause unexpected behavior and should still lead to the correct largest multiple of 3.
Input contains large repeating digit sequences	The remainder calculation after sorting should work correctly, even with repeating sequences.

Empty input list

How to Handle:

Return an empty string as there is no multiple of three that can be formed.

List contains only zeros

How to Handle:

Return '0' as this is the largest multiple of three.

List contains digits that sum to a value not divisible by 3, but removing one or two smallest digits results in a divisible sum

How to Handle:

Iteratively remove the smallest 1 or 2 digits that give remainder 1 or 2 mod 3.

List contains only digits that sum to a value not divisible by 3, and no removal of digits can make it divisible by 3.

How to Handle:

Return an empty string since no multiple of 3 can be formed.

List contains a very large number of digits.

How to Handle:

The solution should be designed to avoid integer overflow when calculating the sum and avoid creating too many copies of sublists.

Input list contains leading zeros after processing.

How to Handle:

Remove leading zeros from the resulting string, unless the entire string becomes empty, in which case it should be '0'.

Input digits are already sorted in descending order.

How to Handle:

The sorting step should not cause unexpected behavior and should still lead to the correct largest multiple of 3.

Input contains large repeating digit sequences

How to Handle:

The remainder calculation after sorting should work correctly, even with repeating sequences.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for each digit in the input array? Can the digits be negative?
What should I return if it's not possible to form a multiple of three with the given digits?
Are the digits provided as integers, or strings? And are they guaranteed to be single digits (0-9)?
If multiple largest multiples of three can be formed, is there any preference for which one to return (e.g., lexicographically largest)?
Does the order of digits in the input array matter? That is, do I need to maintain the relative ordering of the provided digits in the final result?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by forming all possible numbers you can make using the given digits.
This includes single-digit numbers, two-digit numbers, three-digit numbers, and so on, up to using all the digits together.
For each of these numbers you created, check if it can be divided evenly by three (meaning, if you divide by three, there's no remainder).
If a number can be divided by three, compare it to the largest multiple of three you've found so far.
If the new number is bigger than the largest one you've seen, replace the largest one with this new number.
Continue until you've tried all possible number combinations.
The largest multiple of three you have at the end is the answer.

Code Implementation

def largest_multiple_of_three_brute_force(digits):
    largest_multiple = ""

    def generate_combinations(current_combination, remaining_digits):
        nonlocal largest_multiple

        # Convert the current combination to an integer and check divisibility.
        if current_combination:
            number = int("".join(map(str, sorted(current_combination, reverse=True))))
            if number % 3 == 0:
                if largest_multiple == "" or number > int(largest_multiple):
                    largest_multiple = str(number)

        # If we've run out of digits, stop.
        if not remaining_digits:
            return

        # Iterate through the remaining digits to build combinations.
        for i in range(len(remaining_digits)):
            # Recursively generate combinations by including each digit.
            generate_combinations(current_combination + [remaining_digits[i]], remaining_digits[:i] + remaining_digits[i+1:])

    generate_combinations([], digits)

    if largest_multiple == "":
        return ""

    # Handle leading zeros, like "000" should be "0".
    if all(digit == '0' for digit in largest_multiple):
        return "0"

    return largest_multiple

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, add up all the digits to see if the original number (formed by arranging all the digits from largest to smallest) is already divisible by three. If so, you're done: sort the digits in descending order to get the biggest number and return it.
If the sum of the digits isn't divisible by three, find out the remainder when you divide the sum by three. This remainder tells us how much we need to reduce the sum by to make it divisible by three.
If the remainder is one, it means we need to remove one digit that leaves a remainder of one when divided by three, or remove two digits that each leave a remainder of two when divided by three. Pick the option that removes the smallest digits.
If the remainder is two, it means we need to remove one digit that leaves a remainder of two when divided by three, or remove two digits that each leave a remainder of one when divided by three. Pick the option that removes the smallest digits.
After removing the necessary digits, sort the remaining digits in descending order to form the largest possible number.
If all remaining digits are zero, the largest multiple of three is simply zero. If there are no remaining digits, return an empty string.
Construct the final string from the sorted digits, making sure to handle the case where the result is an empty string.

Code Implementation

def largestMultipleOfThree(digits):
    sum_of_digits = sum(digits)

    # If the sum is divisible by three, simply sort and return
    if sum_of_digits % 3 == 0:
        digits.sort(reverse=True)
        result = ''.join(map(str, digits))
        return '0' if result == '0' * len(result) else result

    remainder = sum_of_digits % 3

    # Function to remove digits based on remainder
    def remove_digits(remainder_to_remove):
        group_one = []
        group_two = []
        for digit in sorted(digits):
            if digit % 3 == 1:
                group_one.append(digit)
            elif digit % 3 == 2:
                group_two.append(digit)

        if remainder_to_remove == 1:
            if group_one:
                digits.remove(group_one[0])
                return True
            elif len(group_two) >= 2:
                digits.remove(group_two[0])
                digits.remove(group_two[1])
                return True
        else:
            if group_two:
                digits.remove(group_two[0])
                return True
            elif len(group_one) >= 2:
                digits.remove(group_one[0])
                digits.remove(group_one[1])
                return True
        return False

    # Remove the necessary digits
    if not remove_digits(remainder):
        return ''

    digits.sort(reverse=True)
    result = ''.join(map(str, digits))

    # Handle all zeros case
    if result == '0' * len(result):
        return '0'

    return result

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input list	Return an empty string as there is no multiple of three that can be formed.
List contains only zeros	Return '0' as this is the largest multiple of three.
List contains digits that sum to a value not divisible by 3, but removing one or two smallest digits results in a divisible sum	Iteratively remove the smallest 1 or 2 digits that give remainder 1 or 2 mod 3.
List contains only digits that sum to a value not divisible by 3, and no removal of digits can make it divisible by 3.	Return an empty string since no multiple of 3 can be formed.
List contains a very large number of digits.	The solution should be designed to avoid integer overflow when calculating the sum and avoid creating too many copies of sublists.
Input list contains leading zeros after processing.	Remove leading zeros from the resulting string, unless the entire string becomes empty, in which case it should be '0'.
Input digits are already sorted in descending order.	The sorting step should not cause unexpected behavior and should still lead to the correct largest multiple of 3.
Input contains large repeating digit sequences	The remainder calculation after sorting should work correctly, even with repeating sequences.

Empty input list

How to Handle:

Return an empty string as there is no multiple of three that can be formed.

List contains only zeros

How to Handle:

Return '0' as this is the largest multiple of three.

List contains digits that sum to a value not divisible by 3, but removing one or two smallest digits results in a divisible sum

How to Handle:

Iteratively remove the smallest 1 or 2 digits that give remainder 1 or 2 mod 3.

List contains only digits that sum to a value not divisible by 3, and no removal of digits can make it divisible by 3.

How to Handle:

Return an empty string since no multiple of 3 can be formed.

List contains a very large number of digits.

How to Handle:

The solution should be designed to avoid integer overflow when calculating the sum and avoid creating too many copies of sublists.

Input list contains leading zeros after processing.

How to Handle:

Remove leading zeros from the resulting string, unless the entire string becomes empty, in which case it should be '0'.

Input digits are already sorted in descending order.

How to Handle:

The sorting step should not cause unexpected behavior and should still lead to the correct largest multiple of 3.

Input contains large repeating digit sequences

How to Handle:

The remainder calculation after sorting should work correctly, even with repeating sequences.