Jobs

Interviews

Discussions

Greatest Sum Divisible by Three

Medium

DE Shaw

4 views

Topics:

ArraysDynamic Programming

Given an integer array nums, return the maximum possible sum of elements of the array such that it is divisible by three.

Example 1:

Input: nums = [3,6,5,1,8]
Output: 18
Explanation: Pick numbers 3, 6, 1 and 8 their sum is 18 (maximum sum divisible by 3).

Example 2:

Input: nums = [4]
Output: 0
Explanation: Since 4 is not divisible by 3, do not pick any number.

Example 3:

Input: nums = [1,2,3,4,4]
Output: 12
Explanation: Pick numbers 1, 3, 4 and 4 their sum is 12 (maximum sum divisible by 3).

Constraints:

1 <= nums.length <= 4 * 10⁴
1 <= nums[i] <= 10⁴

Greatest Sum Divisible by Three

Medium

DE Shaw

4 views

Topics:

ArraysDynamic Programming

Given an integer array nums, return the maximum possible sum of elements of the array such that it is divisible by three.

Example 1:

Input: nums = [3,6,5,1,8]
Output: 18
Explanation: Pick numbers 3, 6, 1 and 8 their sum is 18 (maximum sum divisible by 3).

Example 2:

Input: nums = [4]
Output: 0
Explanation: Since 4 is not divisible by 3, do not pick any number.

Example 3:

Input: nums = [1,2,3,4,4]
Output: 12
Explanation: Pick numbers 1, 3, 4 and 4 their sum is 12 (maximum sum divisible by 3).

Constraints:

1 <= nums.length <= 4 * 10⁴
1 <= nums[i] <= 10⁴

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 within the input array? Can the numbers be negative, positive, or zero?
What should I return if no subset of the input array sums to a multiple of three? Should I return 0, null, or throw an exception?
Are there any size constraints on the input array? For example, is it possible for the array to be empty, or very large?
If multiple subsets of the array sum to a multiple of three, should I return the greatest possible sum?
Can I assume the input will always be a valid array of integers?

Brute Force Solution

Approach

The core idea is to explore every single possible group of numbers. For each group, we check if the sum of the numbers is perfectly divisible by three. We then want to find the biggest sum we've seen so far that meets our criteria.

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

Consider all possible combinations of numbers from the given list. This means looking at every possible subset of the list, from a single number to the entire list.
For each combination (subset) that you pick, add up all the numbers in that combination.
Check if the sum you calculated is divisible by three, meaning when you divide by three, there's no remainder left over.
If the sum is divisible by three, remember this sum. If it's the biggest sum you've seen so far that's divisible by three, keep track of it.
Repeat this process for every single combination of numbers you can make from the original list.
After you've checked all the combinations, the largest sum you kept track of is the answer.

Code Implementation

def greatest_sum_divisible_by_three_brute_force(numbers):
    maximum_sum = 0
    number_of_numbers = len(numbers)

    # Iterate through all possible subsets of the input numbers
    for i in range(1 << number_of_numbers):
        current_subset = []
        for j in range(number_of_numbers):
            if (i >> j) & 1:
                current_subset.append(numbers[j])

        # Calculate the sum of the current subset
        current_sum = sum(current_subset)

        #Check if the current sum is divisible by 3
        if current_sum % 3 == 0:

            #Update maximum_sum if needed
            maximum_sum = max(maximum_sum, current_sum)

    return maximum_sum

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(2^n) – The described algorithm considers all possible subsets of the input array of size n. Generating all subsets requires iterating through each element and deciding whether to include it or not, leading to 2^n possible combinations. For each subset, the algorithm calculates the sum, which takes O(n) time in the worst case. Therefore, the overall time complexity is dominated by the subset generation, resulting in O(2^n) as the number of subsets grows exponentially with the input size, dwarfing the linear time sum calculation.

Space Complexity

O(1) – The described solution explores all possible subsets, calculating and comparing sums. While conceptually exploring subsets, the plain English explanation doesn't specify storing each subset explicitly. It only mentions keeping track of the largest sum divisible by three found so far. Thus, the solution only requires a single variable (or a fixed number of variables) to hold this largest sum, regardless of the input list's size N. Therefore, the auxiliary space is constant.

Optimal Solution

Approach

The best way to solve this problem is to keep track of the smallest numbers that leave remainders of 1 and 2 when divided by 3. As we go through the numbers, we update these smallest values, and then use them to figure out if we can improve our total sum to be divisible by 3.

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

Calculate the total sum of all the numbers.
Figure out what the remainder is when the total sum is divided by 3. We only care if the remainder is 1 or 2, since if it is 0 then we are done.
If the remainder is 1, we need to subtract something to make the sum divisible by 3. Check the smallest number that also leaves a remainder of 1 when divided by 3. Subtract this number from the total sum.
There is another way to reduce the remainder to zero: Check the two smallest numbers that leave a remainder of 2 when divided by 3. Subtract both of these numbers from the total sum.
Pick the method that results in the greatest sum. That is, if subtracting the single smallest number that leaves a remainder of 1 gives a larger sum than subtracting the two smallest numbers that leave a remainder of 2, then go with the first method. Otherwise, use the second method.
If the remainder is 2, we need to subtract something to make the sum divisible by 3. Check the smallest number that leaves a remainder of 2 when divided by 3. Subtract this number from the total sum.
Like before, there is another way to reduce the remainder to zero: Check the two smallest numbers that leave a remainder of 1 when divided by 3. Subtract both of these numbers from the total sum.
Pick the method that results in the greatest sum. That is, if subtracting the single smallest number that leaves a remainder of 2 gives a larger sum than subtracting the two smallest numbers that leave a remainder of 1, then go with the first method. Otherwise, use the second method.
Return the final sum. If it turns out that it is not possible to get a sum divisible by 3, return 0.

Code Implementation

def greatest_sum_divisible_by_three(numbers):
    total_sum = sum(numbers)

    remainder = total_sum % 3

    if remainder == 0:
        return total_sum

    smallest_remainder_one = float('inf')
    second_smallest_remainder_one = float('inf')
    smallest_remainder_two = float('inf')
    second_smallest_remainder_two = float('inf')

    for number in numbers:
        if number % 3 == 1:
            if number < smallest_remainder_one:
                second_smallest_remainder_one = smallest_remainder_one
                smallest_remainder_one = number
            elif number < second_smallest_remainder_one:
                second_smallest_remainder_one = number
        elif number % 3 == 2:
            if number < smallest_remainder_two:
                second_smallest_remainder_two = smallest_remainder_two
                smallest_remainder_two = number
            elif number < second_smallest_remainder_two:
                second_smallest_remainder_two = number

    if remainder == 1:
        # We need to subtract either one number with remainder 1,
        # or two numbers with remainder 2.
        option1 = total_sum - smallest_remainder_one
        option2 = total_sum - (smallest_remainder_two + second_smallest_remainder_two)

        # Handle edge cases where we don't have enough numbers.
        if smallest_remainder_one == float('inf'):
            option1 = float('-inf')
        if smallest_remainder_two == float('inf') or second_smallest_remainder_two == float('inf'):
            option2 = float('-inf')

        return max(option1, option2) if max(option1, option2) > 0 else 0

    else:
        # We need to subtract either one number with remainder 2,
        # or two numbers with remainder 1.
        option1 = total_sum - smallest_remainder_two
        option2 = total_sum - (smallest_remainder_one + second_smallest_remainder_one)

        # Handle edge cases where we don't have enough numbers.
        if smallest_remainder_two == float('inf'):
            option1 = float('-inf')

        if smallest_remainder_one == float('inf') or second_smallest_remainder_one == float('inf'):
            option2 = float('-inf')

        # Return the greater of the two sums
        return max(option1, option2) if max(option1, option2) > 0 else 0

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of size n once to calculate the total sum and update the smallest values for remainders 1 and 2. Finding the minimum values for remainders 1 and 2 also requires, at most, iterating through the input array once. The subsequent calculations (remainder checks and subtractions) involve constant time operations. Therefore, the time complexity is dominated by the single iteration through the input array, resulting in O(n) time complexity.

Space Complexity

O(1) – The algorithm uses a fixed number of variables to store the smallest numbers with remainders 1 and 2. These variables (at most four) do not depend on the input size N, which represents the number of elements in the input array. Therefore, the auxiliary space required remains constant irrespective of the input array size. The space complexity is thus O(1).

Edge Cases

Case	How to Handle
Empty input array	Return 0 since no sum can be formed.
Array with only one element	If the single element is divisible by 3, return it; otherwise, return 0.
Array with all negative numbers	Find the largest sum of numbers divisible by 3, handling negative modulo appropriately.
Array with all zeros	Return 0 since the greatest sum divisible by 3 is 0.
Array with very large numbers that could lead to integer overflow	Use long data type to store the intermediate sums.
Array where no combination of numbers sums to a multiple of 3	Return 0, as there's no valid sum.
Array with a mix of positive and negative numbers, with a large range	The dynamic programming approach correctly considers both positive and negative contributions to the remainders.
Maximum array size causing memory issues	The constant space dynamic programming approach should handle large arrays without memory overflow.

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 within the input array? Can the numbers be negative, positive, or zero?
What should I return if no subset of the input array sums to a multiple of three? Should I return 0, null, or throw an exception?
Are there any size constraints on the input array? For example, is it possible for the array to be empty, or very large?
If multiple subsets of the array sum to a multiple of three, should I return the greatest possible sum?
Can I assume the input will always be a valid array of integers?

Brute Force Solution

Approach

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

Consider all possible combinations of numbers from the given list. This means looking at every possible subset of the list, from a single number to the entire list.
For each combination (subset) that you pick, add up all the numbers in that combination.
Check if the sum you calculated is divisible by three, meaning when you divide by three, there's no remainder left over.
If the sum is divisible by three, remember this sum. If it's the biggest sum you've seen so far that's divisible by three, keep track of it.
Repeat this process for every single combination of numbers you can make from the original list.
After you've checked all the combinations, the largest sum you kept track of is the answer.

Code Implementation

def greatest_sum_divisible_by_three_brute_force(numbers):
    maximum_sum = 0
    number_of_numbers = len(numbers)

    # Iterate through all possible subsets of the input numbers
    for i in range(1 << number_of_numbers):
        current_subset = []
        for j in range(number_of_numbers):
            if (i >> j) & 1:
                current_subset.append(numbers[j])

        # Calculate the sum of the current subset
        current_sum = sum(current_subset)

        #Check if the current sum is divisible by 3
        if current_sum % 3 == 0:

            #Update maximum_sum if needed
            maximum_sum = max(maximum_sum, current_sum)

    return maximum_sum

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Calculate the total sum of all the numbers.
Figure out what the remainder is when the total sum is divided by 3. We only care if the remainder is 1 or 2, since if it is 0 then we are done.
If the remainder is 1, we need to subtract something to make the sum divisible by 3. Check the smallest number that also leaves a remainder of 1 when divided by 3. Subtract this number from the total sum.
There is another way to reduce the remainder to zero: Check the two smallest numbers that leave a remainder of 2 when divided by 3. Subtract both of these numbers from the total sum.
Pick the method that results in the greatest sum. That is, if subtracting the single smallest number that leaves a remainder of 1 gives a larger sum than subtracting the two smallest numbers that leave a remainder of 2, then go with the first method. Otherwise, use the second method.
If the remainder is 2, we need to subtract something to make the sum divisible by 3. Check the smallest number that leaves a remainder of 2 when divided by 3. Subtract this number from the total sum.
Like before, there is another way to reduce the remainder to zero: Check the two smallest numbers that leave a remainder of 1 when divided by 3. Subtract both of these numbers from the total sum.
Pick the method that results in the greatest sum. That is, if subtracting the single smallest number that leaves a remainder of 2 gives a larger sum than subtracting the two smallest numbers that leave a remainder of 1, then go with the first method. Otherwise, use the second method.
Return the final sum. If it turns out that it is not possible to get a sum divisible by 3, return 0.

Code Implementation

def greatest_sum_divisible_by_three(numbers):
    total_sum = sum(numbers)

    remainder = total_sum % 3

    if remainder == 0:
        return total_sum

    smallest_remainder_one = float('inf')
    second_smallest_remainder_one = float('inf')
    smallest_remainder_two = float('inf')
    second_smallest_remainder_two = float('inf')

    for number in numbers:
        if number % 3 == 1:
            if number < smallest_remainder_one:
                second_smallest_remainder_one = smallest_remainder_one
                smallest_remainder_one = number
            elif number < second_smallest_remainder_one:
                second_smallest_remainder_one = number
        elif number % 3 == 2:
            if number < smallest_remainder_two:
                second_smallest_remainder_two = smallest_remainder_two
                smallest_remainder_two = number
            elif number < second_smallest_remainder_two:
                second_smallest_remainder_two = number

    if remainder == 1:
        # We need to subtract either one number with remainder 1,
        # or two numbers with remainder 2.
        option1 = total_sum - smallest_remainder_one
        option2 = total_sum - (smallest_remainder_two + second_smallest_remainder_two)

        # Handle edge cases where we don't have enough numbers.
        if smallest_remainder_one == float('inf'):
            option1 = float('-inf')
        if smallest_remainder_two == float('inf') or second_smallest_remainder_two == float('inf'):
            option2 = float('-inf')

        return max(option1, option2) if max(option1, option2) > 0 else 0

    else:
        # We need to subtract either one number with remainder 2,
        # or two numbers with remainder 1.
        option1 = total_sum - smallest_remainder_two
        option2 = total_sum - (smallest_remainder_one + second_smallest_remainder_one)

        # Handle edge cases where we don't have enough numbers.
        if smallest_remainder_two == float('inf'):
            option1 = float('-inf')

        if smallest_remainder_one == float('inf') or second_smallest_remainder_one == float('inf'):
            option2 = float('-inf')

        # Return the greater of the two sums
        return max(option1, option2) if max(option1, option2) > 0 else 0

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return 0 since no sum can be formed.
Array with only one element	If the single element is divisible by 3, return it; otherwise, return 0.
Array with all negative numbers	Find the largest sum of numbers divisible by 3, handling negative modulo appropriately.
Array with all zeros	Return 0 since the greatest sum divisible by 3 is 0.
Array with very large numbers that could lead to integer overflow	Use long data type to store the intermediate sums.
Array where no combination of numbers sums to a multiple of 3	Return 0, as there's no valid sum.
Array with a mix of positive and negative numbers, with a large range	The dynamic programming approach correctly considers both positive and negative contributions to the remainders.
Maximum array size causing memory issues	The constant space dynamic programming approach should handle large arrays without memory overflow.