Largest Multiple Of Three - Leetcode Solution

Problem Statement: Given an integer array of non-negative integers, find the largest multiple of 3 that can be formed from array elements. Return an array of integers representing the digits of that multiple. If no such multiple can be formed, return an empty array.

Example 1: Input: [8, 1, 9] Output: [9, 8, 1] Explanation: The largest multiple of 3 that can be formed by the elements of the array is 981.

Example 2: Input: [1, 0, 0, 0] Output: [0, 0, 0] Explanation: The largest multiple of 3 that can be formed by the elements of the array is 0.

Approach: The first step in solving this problem involves finding the remainder when the sum of all array elements is divided by 3. There are 3 possibilities:

• Remainder = 0: In this case, we can simply sort the array in decreasing order and return it.
• Remainder = 1: We remove the smallest digit that gives a remainder of 1 when divided by 3. If there is only one digit that gives a remainder of 1, we remove the smallest digit. If there are two digits that give a remainder of 1, we remove the two smallest digits. We then sort the resulting array in decreasing order and return it.
• Remainder = 2: We remove the smallest digit that gives a remainder of 2 when divided by 3. If there is only one digit that gives a remainder of 2, we remove the smallest digit. If there are two digits that give a remainder of 2, we remove the two smallest digits. We then sort the resulting array in decreasing order and return it.

Algorithm:

1. Find the remainder when the sum of all array elements is divided by 3. Store the numbers in three buckets based on their remainders (0, 1, or 2).
2. Sort the numbers in each bucket in decreasing order.
3. If remainder is 0, return all the numbers in the buckets in decreasing order.
4. If remainder is 1, attempt to return all the numbers in the 0 or 2 bucket. If that is not possible, remove the two smallest numbers in the 1 bucket and return the remaining numbers in the 0 or 2 bucket (if any exist).
5. If remainder is 2, attempt to return all the numbers in the 0 or 1 bucket. If that is not possible, remove the two smallest numbers in the 2 bucket and return the remaining numbers in the 0 or 1 bucket (if any exist).

Code:

class Solution { public int[] largestMultipleOfThree(int[] nums) { Arrays.sort(nums); int sum = 0; for (int num : nums) { sum += num; } if (sum % 3 == 1) { if (!removeOne(nums)) { removeTwo(nums); } } else if (sum % 3 == 2) { if (!removeTwo(nums)) { removeOne(nums); } } Arrays.sort(nums); int n = nums.length; int i = n - 1; while (i >= 0 && nums[i] == 0) { i--; } if (i < 0) { return new int[]{0}; } int[] res = new int[i + 1]; for (int j = 0; j <= i; j++) { res[j] = nums[i - j]; } return res; }

private boolean removeOne(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] % 3 == 1) {
            nums[i] = -1;
            return true;
        }
    }
    return false;
}

private boolean removeTwo(int[] nums) {
    int count = 0;
    for (int i = 0; i < nums.length && count < 2; i++) {
        if (nums[i] % 3 == 2) {
            nums[i] = -1;
            count++;
        }
    }
    if (count == 2) {
        return true;
    } else {
        return removeOne(nums);
    }
}

}

Time Complexity: The time complexity of the above solution is O(n log n), where n is the length of the nums array. This is because we are sorting the array twice, which takes O(n log n) time.

Space Complexity: The space complexity of the above solution is O(n), where n is the length of the nums array. This is because we are using an array to store the digits of the largest multiple of 3 that can be formed.

1