Given an array of integers, find the LARGEST number using the digits of the array such that it is divisible by 3

Question

E.g.: Array: 4,3,0,1,5 {Assume all digits are >=0. Also each element in array correspond to a digit. i.e. each element on the array is between 0 and 9. }

In the above array, the largest number is: 5430 {using digits 5, 4, 3 and 0 from the array}

My Approach:

For divisibility by 3, we need the sum of digits to be divisible by 3. So,

1. Step-1: Remove all the zeroes from the array.
2. Step-2: These zeroes will come at the end. {Since they dont affect the sum and we have to find the largest number}
3. Step-3: Find the subset of the elements of array (excluding zeroes) such that the number of digits is MAXIMUM and also that the sum of digits is MAXIMUM and the sum is divisible by 3.
4. STEP-4: The required digit consists of the digits in the above found set in decreasing order.

So, the main step is STEP-3 i.e. How to find the subset such that it contains MAXIMUM possible number of elements such that their sum is MAX and is divisible by 3 .

I was thinking, maybe Step-3 could be done by GREEDY CHOICE of taking all the elements and keep on removing the smallest element in the set till the sum is divisible by 3.

But i am not convinced that this GREEDY choice will work.

Please tell if my approach is correct. If it is, then please suggest as to how to do Step-3 ?

Also, please suggest any other possible/efficient algorithm.

Answer 1

Observation: If you can get a number that is divisible by 3, you need to remove at most 2 numbers, to maintain optimal solution.

A simple O(n^2) solution will be to check all possibilities to remove 1 number, and if none is valid, check all pairs (There are O(n^2) of those).

---

EDIT:
O(n) solution: Create 3 buckets - bucket1, bucket2, bucket0. Each will denote the modulus 3 value of the numbers. Ignore bucket0 in the next algorithm.

Let the sum of the array be sum.

If sum % 3 ==0: we are done.
else if sum % 3 == 1:
  if there is a number in bucket1 - chose the minimal
  else: take 2 minimals from bucket 2
else if sum % 3 == 2
  if there is a number in bucket2 - chose the minimal
  else: take 2 minimals from bucket1  

Note: You don't actually need the bucket, to achieve O(1) space - you need only the 2 minimal values from bucket1 and bucket2, since it is the only number we actually used from these buckets.

Example:

arr = { 3, 4, 0, 1, 5 }
bucket0 = {3,0} ; bucket1 = {4,1} bucket2 = { 5 }
sum = 13 ; sum %3 = 1
bucket1 is not empty - chose minimal from it (1), and remove it from the array.
result array = { 3, 4, 0, 5 } 
proceed to STEP 4 "as planned"

Answer 2

Greedy choice definitely doesn't work: consider the set {5, 2, 1}. You'd remove the 1 first, but you should remove the 2.

I think you should work out the sum of the array modulo 3, which is either 0 (you're finished), or 1, or 2. Then you're looking to remove the minimal subset whose sum modulo 3 is 1 or 2.

I think that's fairly straightforward, so no real need for dynamic programming. Do it by removing one number with that modulus if possible, otherwise do it by removing two numbers with the other modulus. Once you know how many to remove, choose the smallest possible. You'll never need to remove three numbers.

You don't need to treat 0 specially, although if you're going to do that then you can further reduce the set under consideration in step 3 if you temporarily remove all 0, 3, 6, 9 from it.

Putting it all together, I would probably:

• Sort the digits, descending.
• Calculate the modulus. If 0, we're finished.
• Try to remove a digit with that modulus, starting from the end. If successful, we're finished.
• Remove two digits with negative-that-modulus, starting from the end. This always succeeds, so we're finished.
• We might be left with an empty array (e.g. if the input is 1, 1), in which case the problem was impossible. Otherwise, the array contains the digits of our result.

Time complexity is O(n) provided that you do a counting sort in step 1. Which you certainly can since the values are digits.