D
DevExCode

LeetCode 1363: Largest Multiple of Three Solution

Master LeetCode problem 1363 (Largest Multiple of Three), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1363. Largest Multiple of Three

Hard
ArrayMathDynamic ProgrammingGreedySorting

Problem Explanation

Explanation:

To find the largest multiple of three that can be formed by concatenating some of the given digits, we need to consider the remainder when dividing the sum of all digits by 3. Based on the remainder, we will decide which digits to remove in order to form the largest multiple of three.

  1. Calculate the sum of all digits.
  2. Calculate the remainder when dividing the sum by 3.
  3. If the remainder is 1:
    • Try to remove one digit with a remainder of 1 (if there are multiple, remove the smallest) or two digits with a remainder of 2 (if there are enough) to form a multiple of three.
    • If not possible, remove two digits with a remainder of 1.
  4. If the remainder is 2:
    • Try to remove one digit with a remainder of 2 (if there are multiple, remove the smallest) or two digits with a remainder of 1 (if there are enough) to form a multiple of three.
    • If not possible, remove two digits with a remainder of 2.
  5. Sort the remaining digits in descending order and concatenate them to form the largest multiple of three.

:

Solution Code

class Solution {
    public String largestMultipleOfThree(int[] digits) {
        int sum = 0;
        int[] count = new int[10];
        
        for (int digit : digits) {
            sum += digit;
            count[digit]++;
        }
        
        if (sum % 3 == 1) {
            if (removeDigits(count, 1)) {
                return buildResult(count);
            }
            removeDigits(count, 2);
        } else if (sum % 3 == 2) {
            if (removeDigits(count, 2)) {
                return buildResult(count);
            }
            removeDigits(count, 1);
        }
        
        return buildResult(count);
    }
    
    private boolean removeDigits(int[] count, int rem) {
        for (int i = rem; i <= 9; i += 3) {
            while (count[i] > 0) {
                count[i]--;
                if ((i - rem) % 3 == 0) {
                    return true;
                }
            }
        }
        return false;
    }
    
    private String buildResult(int[] count) {
        StringBuilder sb = new StringBuilder();
        for (int i = 9; i >= 0; i--) {
            while (count[i] > 0) {
                sb.append(i);
                count[i]--;
            }
        }
        if (sb.length() > 0 && sb.charAt(0) == '0') {
            return "0";
        }
        return sb.toString();
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 1363 (Largest Multiple of Three)?

This page provides optimized solutions for LeetCode problem 1363 (Largest Multiple of Three) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1363 (Largest Multiple of Three)?

The time complexity for LeetCode 1363 (Largest Multiple of Three) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1363 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1363 in Java, C++, or Python.

Back to LeetCode Solutions