Largest multiple of three

Array Math Dynamic Programming Greedy Sorting

33.1% acceptance

Feb 25, 2026

628

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.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn largest_multiple_of_three(mut digits: Vec<i32>) -> String {
    digits.sort_unstable_by(|a, b| b.cmp(a)); // descending
    let sum: i32 = digits.iter().sum();
    let rem = sum % 3;
    // Helper: remove first (smallest) digit with given remainder
    fn remove_one(digits: &mut Vec<i32>, r: i32) -> bool {
      for i in (0..digits.len()).rev() {
        if digits[i] % 3 == r {
          digits.remove(i);
          return true;
        }
      }
      false
    }
    if rem == 1 {
      // Try remove one digit with rem 1
      let mut d1 = digits.clone();
      if !remove_one(&mut d1, 1) {
        // remove two digits with rem 2
        if !remove_one(&mut digits, 2) || !remove_one(&mut digits, 2) {
          return String::new();
        }
      } else {
        digits = d1;
      }
    } else if rem == 2 {
      let mut d1 = digits.clone();
      if !remove_one(&mut d1, 2) {
        if !remove_one(&mut digits, 1) || !remove_one(&mut digits, 1) {
          return String::new();
        }
      } else {
        digits = d1;
      }
    }
    if digits.is_empty() { return String::new(); }
    if digits[0] == 0 { return "0".to_string(); }
    digits.iter().map(|d| char::from_digit(*d as u32, 10).unwrap()).collect()
  }
}