Largest Multiple of Three - Practice Coding Problems

Largest Multiple of Three - Problem

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.

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

Input & Output

Example 1 — Basic Case

$ Input: digits = [8,1,9]

› Output: 981

💡 Note: Sum = 8+1+9 = 18, which is divisible by 3. Use all digits arranged in descending order to get the largest number: 981.

Example 2 — Need to Remove Digits

$ Input: digits = [8,6,7,1,0]

› Output: 8760

💡 Note: Sum = 22, remainder = 1. Remove the smallest digit with remainder 1 (which is 1). Remaining digits [8,6,7,0] sum to 21, divisible by 3. Result: 8760.

Example 3 — All Zeros Case

$ Input: digits = [0,0,0]

› Output: 0

💡 Note: Sum = 0, divisible by 3. All digits are zero, so return single '0' to avoid leading zeros.

Constraints

1 ≤ digits.length ≤ 10⁴
0 ≤ digits[i] ≤ 9

Visualization

Tap to expand

Understanding the Visualization

Input

Array of digits [8,1,9]

Process

Check sum divisibility by 3, arrange optimally

Output

Largest multiple of 3: 981

Key Takeaway

🎯 Key Insight: Use the divisibility rule for 3 (sum of digits) combined with greedy digit arrangement to construct the optimal solution efficiently.

Asked in

G Google 45 a Amazon 38 M Microsoft 32 Apple 25

The key insight is that a number is divisible by 3 if and only if the sum of its digits is divisible by 3. The optimal greedy approach counts digit frequencies, strategically removes minimal digits to achieve divisibility by 3, then arranges remaining digits in descending order. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Greedy - Mathematical Approach	O(n)	O(1)	Use divisibility rules and digit frequency counting to construct optimal result
Brute Force - Try All Combinations	O(2ⁿ × n! × n)	O(2ⁿ × n)	Generate all possible number combinations and find the largest multiple of three

Greedy - Mathematical Approach — Algorithm Steps

Count frequency of each digit 0-9
Calculate total sum of all digits
If sum % 3 != 0, remove minimum digits to make it divisible
Arrange remaining digits in descending order
Handle edge case of all zeros

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Digits

Count frequency of each digit 0-9

Check Sum

Calculate total sum and remainder when divided by 3

Remove Strategically

Remove minimum digits to make sum divisible by 3

Arrange Descending

Build largest number from remaining digits

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* solution(int* digits, int digitsSize) {
    if (digitsSize == 0) {
        char* result = (char*)malloc(1);
        result[0] = '\0';
        return result;
    }
    
    // Count frequency of each digit
    int count[10] = {0};
    int totalSum = 0;
    
    for (int i = 0; i < digitsSize; i++) {
        count[digits[i]]++;
        totalSum += digits[i];
    }
    
    // If sum is already divisible by 3, use all digits
    int remainder = totalSum % 3;
    
    if (remainder == 1) {
        // Remove one digit with remainder 1, or two digits with remainder 2
        if (count[1] > 0) {
            count[1]--;
        } else if (count[4] > 0) {
            count[4]--;
        } else if (count[7] > 0) {
            count[7]--;
        } else {
            // Remove two digits with remainder 2
            int removed = 0;
            int digits_to_remove[] = {2, 5, 8};
            for (int j = 0; j < 3 && removed < 2; j++) {
                while (count[digits_to_remove[j]] > 0 && removed < 2) {
                    count[digits_to_remove[j]]--;
                    removed++;
                }
            }
        }
    } else if (remainder == 2) {
        // Remove one digit with remainder 2, or two digits with remainder 1
        if (count[2] > 0) {
            count[2]--;
        } else if (count[5] > 0) {
            count[5]--;
        } else if (count[8] > 0) {
            count[8]--;
        } else {
            // Remove two digits with remainder 1
            int removed = 0;
            int digits_to_remove[] = {1, 4, 7};
            for (int j = 0; j < 3 && removed < 2; j++) {
                while (count[digits_to_remove[j]] > 0 && removed < 2) {
                    count[digits_to_remove[j]]--;
                    removed++;
                }
            }
        }
    }
    
    // Build result string from largest to smallest digit
    char* result = (char*)malloc(1000);
    int pos = 0;
    
    for (int digit = 9; digit >= 0; digit--) {
        for (int i = 0; i < count[digit]; i++) {
            result[pos++] = '0' + digit;
        }
    }
    
    result[pos] = '\0';
    
    if (pos == 0) {
        strcpy(result, "");
        return result;
    }
    
    // Handle case where result is all zeros
    if (result[0] == '0') {
        strcpy(result, "0");
    }
    
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for [1,2,3] format
    int digits[100];
    int digitsSize = 0;
    
    char* ptr = strchr(line, '[');
    if (ptr) {
        ptr++;
        char* token = strtok(ptr, ",]");
        while (token) {
            digits[digitsSize++] = atoi(token);
            token = strtok(NULL, ",]");
        }
    }
    
    char* result = solution(digits, digitsSize);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to count digits, then constant time operations

✓ Linear Growth

Space Complexity

O(1)

Fixed-size array to count digit frequencies (0-9)

✓ Linear Space

42.0K Views

Medium Frequency

~25 min Avg. Time

894 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy - Mathematical Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler