Find the largest multiple of 3.

Given an array of non-negative integers. Find the largest multiple of 3 that can be formed from array elements.

For example, if the input array is {8, 1, 9}, the output should be “9 8 1”, and if the input array is {8, 1, 7, 6, 0}, output should be “8 7 6 0”.

Solution:

Number three has some special property
– A number is multiple of 3 if and only if the sum of digits of number is multiple of 3. For example, let us consider 8760, it is a multiple of 3 because sum of digits is 8 + 7+ 6+ 0 = 21, which is a multiple of 3.
– If a number is multiple of 3, then all permutations of it are also multiple of 3. For example, since 6078 is a multiple of 3, the numbers 8760, 7608, 7068, ….. are also multiples of 3.
– We get the same remainder when we divide the number and sum of digits of the number. For example, if divide number 151 and sum of it digits 7, by 3, we get the same remainder 1.

Algorithm:

• First sort the array in ascending order
• Take three queues,
  • 1. Queue0 – To hold digit % 3 == 0
  • 2. Queue1 – To hold digit % 3 == 1
  • 3. Queue2 – To hold digit % 3 == 2
• Iterate array from start to end
  • Divide digit by 3 and put in respective queues based on remainder
  • And calculate sum_of_digits
• Calculate remainder = sum_of_digits % 3
• if remainder == 1
  • Dequeue one element from Queue1 or two dequeue from Queue2
  • (Why Queue2? because 5 + 2 = 7, 7 % 3 = 1)
• else if remainder == 2
  • Dequeue one element from Queue2 or two dequeue from Queue1
• Merge Queue0, Queue1 and Queue2 into one list
• sort merge list in descending order
• return merged sorted order

Latest Source Code:
Github: LargestMultipleOfThree.java

Output:

8760