Largest Multiple of Three

Hard
714.

Largest Multiple of Three

Largest Multiple of Three is a hard coding problem on arrays, dynamic programming and math, asked in Amazon, Google and Meta interviews.

Given an array of digits, concatenate some of them (in any order, using each at most as many times as it appears) to form the largest possible number that is divisible by three.

Return it as a string without leading zeros, or "0" if the best answer is zero, or the empty string if no multiple of three can be formed.

Example 1

Input
digits = [8,1,9]
Output
981
Explanation
8 + 1 + 9 = 18 is already divisible by 3, so use every digit in descending order.

Example 2

Input
digits = [8,6,7,1,0]
Output
8760
Explanation
The total is 22; dropping the 1 makes it 21 and leaves the largest arrangement.

Example 3

Input
digits = [1]
Output
Explanation
Nothing can be formed.

Constraints

  • 1 <= digits.length <= 10000
  • 0 <= digits[i] <= 9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} digits
 * @return {string}
 */
var largestMultipleOfThree = function(digits) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Largest Multiple of Three — Solution in Python, Java & C++

Largest Multiple of Three solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Largest Multiple of Three is a hard coding problem on arrays, dynamic programming and math, asked in Amazon, Google and Meta interviews.

Problem statement

Given an array of digits, concatenate some of them (in any order, using each at most as many times as it appears) to form the largest possible number that is divisible by three.

Return it as a string without leading zeros, or "0" if the best answer is zero, or the empty string if no multiple of three can be formed.

Example 1

Input: digits = [8,1,9]
Output: 981
Explanation: 8 + 1 + 9 = 18 is already divisible by 3, so use every digit in descending order.

Example 2

Input: digits = [8,6,7,1,0]
Output: 8760
Explanation: The total is 22; dropping the 1 makes it 21 and leaves the largest arrangement.

Example 3

Input: digits = [1]
Output: 
Explanation: Nothing can be formed.

Constraints

  • 1 <= digits.length <= 10000
  • 0 <= digits[i] <= 9

Hints for Largest Multiple of Three

  1. Hint 1

    A number is divisible by three exactly when its digit sum is — and the order of the digits does not affect the sum.

  2. Hint 2

    So keep as many digits as possible, then fix the remainder by deleting the fewest, smallest digits.

  3. Hint 3

    If the remainder is r, either delete one digit congruent to r, or two digits congruent to 3 - r. Prefer deleting one.

How to solve Largest Multiple of Three

Divisibility depends only on the multiset of digits, while size depends first on how many digits survive and then on their descending order. So delete as few digits as possible — and among those, the smallest ones.

Approach

  1. Tally the digits and compute the total sum; let r = sum % 3.
  2. If r != 0, try deleting one digit congruent to r modulo 3, scanning r, r+3, r+6 so the smallest goes first.
  3. If there is none, delete two digits congruent to 3 - r, again smallest first. If two cannot be found, return "".
  4. Emit the remaining digits from 9 down to 0; if the result is empty return "", and if it starts with 0 the answer is "0".

Why it works

Deleting one digit beats deleting two, and within a fixed deletion count the surviving number is largest when the deleted digits are smallest and the survivors are sorted descending. One deletion congruent to r or two congruent to 3 - r are the only ways to shift the remainder to zero while removing at most two digits, and removing three or more is never necessary when either option exists.

Complexity

  • Time — O(n + 10)
  • Space — O(10)

Pitfalls

  • Deleting the largest matching digit shrinks the answer unnecessarily.
  • A leading zero means every surviving digit is zero, which must collapse to "0" rather than "000".
  • Sorting the whole array is fine but a 10-slot tally is both simpler and faster.

Reference solution

Python

from typing import List

def largestMultipleOfThree(digits: List[int]) -> str:
    count = [0] * 10
    total = 0
    for d in digits:
        count[d] += 1
        total += d
    r = total % 3
    if r != 0:
        removed = False
        for d in range(r, 10, 3):
            if count[d] > 0:
                count[d] -= 1
                removed = True
                break
        if not removed:
            need = 2
            for d in range((3 - r) % 3, 10, 3):
                while count[d] > 0 and need > 0:
                    count[d] -= 1
                    need -= 1
            if need > 0:
                return ""
    out = "".join(str(d) * count[d] for d in range(9, -1, -1))
    if not out:
        return ""
    if out[0] == "0":
        return "0"
    return out

Java

public static String largestMultipleOfThree(int[] digits) {
    int[] count = new int[10];
    int sum = 0;
    for (int d : digits) { count[d]++; sum += d; }
    int r = sum % 3;
    if (r != 0) {
        boolean removed = false;
        for (int d = r; d <= 9; d += 3) {
            if (count[d] > 0) { count[d]--; removed = true; break; }
        }
        if (!removed) {
            int need = 2;
            for (int d = (3 - r) % 3; d <= 9 && need > 0; d += 3) {
                while (count[d] > 0 && need > 0) { count[d]--; need--; }
            }
            if (need > 0) return "";
        }
    }
    StringBuilder sb = new StringBuilder();
    for (int d = 9; d >= 0; d--) {
        for (int k = 0; k < count[d]; k++) sb.append((char) ('0' + d));
    }
    String out = sb.toString();
    if (out.isEmpty()) return "";
    if (out.charAt(0) == '0') return "0";
    return out;
}

C++

string largestMultipleOfThree(vector<int>& digits) {
    vector<int> count(10, 0);
    int sum = 0;
    for (int d : digits) { count[d]++; sum += d; }
    int r = sum % 3;
    if (r != 0) {
        bool removed = false;
        for (int d = r; d <= 9; d += 3) {
            if (count[d] > 0) { count[d]--; removed = true; break; }
        }
        if (!removed) {
            int need = 2;
            for (int d = (3 - r) % 3; d <= 9 && need > 0; d += 3) {
                while (count[d] > 0 && need > 0) { count[d]--; need--; }
            }
            if (need > 0) return "";
        }
    }
    string out;
    for (int d = 9; d >= 0; d--) {
        for (int k = 0; k < count[d]; k++) out += (char) ('0' + d);
    }
    if (out.empty()) return "";
    if (out[0] == '0') return "0";
    return out;
}

JavaScript

var largestMultipleOfThree = function(digits) {
    var count = [];
    for (var t = 0; t < 10; t++) count.push(0);
    var sum = 0;
    for (var i = 0; i < digits.length; i++) { count[digits[i]]++; sum += digits[i]; }
    var r = sum % 3;
    if (r !== 0) {
        var removed = false;
        for (var d = r; d <= 9; d += 3) {
            if (count[d] > 0) { count[d]--; removed = true; break; }
        }
        if (!removed) {
            var need = 2;
            for (var e = (3 - r) % 3; e <= 9 && need > 0; e += 3) {
                while (count[e] > 0 && need > 0) { count[e]--; need--; }
            }
            if (need > 0) return "";
        }
    }
    var out = "";
    for (var g = 9; g >= 0; g--) {
        for (var k = 0; k < count[g]; k++) out += String(g);
    }
    if (out.length === 0) return "";
    if (out.charAt(0) === "0") return "0";
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming