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.

Chambertin

What about brute force generating all the possibilities ? That is generatif all of the combination which are divisible by 3, and then take the largest ? – Flanigan

step 3 is a bit similar subset-sum problem, but it also smells easier (so it might be solveable polynomially after all). But I doubt greedy will work here. – Diaphone

@Flanigan : Yes, Brute Force is always an option. But i was hinking if it could be done in some efficient way. – Chambertin

@amit: If we use subset-sum approach, then we will have to consider all multiples of 3: 3, 2*3, 3*3, 4*3 .. and so on... So i guess that would then become exponential only. – Chambertin

Here is my idea : You remove the zeros, they'll be added at the end as you said. N non-zero digits remain You then generate all the possibilities with the maximum length N. if you find something, you take the maximum value. Maybe sorting the digits in descending order can be faster. If you don't find something, you look for all the possibilities with length N-1, and so on until you find something. – Flanigan

By the way, you did not give us info on how fast the algorithm should run, nor how large the set of digits can be, do you have these information ? – Flanigan

10%3 == 1. 100%3 == 1 as well – Stoddard

@Flanigan : No, I dont have these info. Just for the sake of simplicity, You may assume that they are not very large numbers... Also, i was just browsing, where i found some problem which was reduced to this problem.. so i dont even have the idea about the best possible running time. – Chambertin

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"

Diaphone

I didn't completely get your O(n^2) approach. You said to first check all possibilities to remove 1 number . That's fine . But what after that ? How will checking for pairs give me the answer ? – Chambertin

@user1599964: You need to remove at most 2 numbers, if you cannot achieve a number divisible by 3 by removing 3 numbers - you cannot get it at all. – Diaphone

@user1599964: Using the above observation - you can get an O(n) solution. I added it in an edit. – Diaphone

Great ! Simple and efficient ! Thanks ! Your's and Steve's answers are the same .. Thanks Again ! – Chambertin

Two points: You can do it in O(n) time, and you need to remove at most one point (except in corner cases). See below for my answer. – Beilul

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.

Evolutionist

Great ! Your's and Amit's solution are identical. Thanks for the great and yet simple algo ! – Chambertin

Yeah, I was writing mine as amit was editing his. The only difference is that he divides into three buckets by modulus, whereas I'm a mathematician, so I can't count to 3 and I just leave them all in one array ;-) – Evolutionist

Answer 3

What do you think about this:

first sort an array elements by value

sum up all numbers
- if sum's remainder after division by 3 is equal to 0, just return the sorted
  array
- otherwise
    - if sum of remainders after division by 3 of all the numbers is smaller
      than the remainder of their sum, there is no solution
    - otherwise
        - if it's equal to 1, try to return the smallest number with remainder
          equal to 1, or if no such, try two smallest with remainder equal to 2,
          if no such two (I suppose it can happen), there's no solution
        - if it's equal to 2, try to return the smallest number with remainder
          equal to 2, or if no such, try two smallest with remainder equal to 1,
          if no such two, there's no solution

first sort an array elements by remainder of division by 3 ascending then each subset of equal remainder sort by value descending

N

Great ! Seems all the 3 solutions are same.. Simple and Efficient ! – Chambertin

Answer 4

First, this problem reduces to maximizing the number of elements selected such that their sum is divisible by 3.

Trivial: Select all numbers divisible by 3 (0,3,6,9).

Le a be the elements that leave 1 as remainder, b be the elements that leave 2 as remainder. If (|a|-|b|)%3 is 0, then select all elements from both a and b. If (|a|-|b|)%3 is 1, select all elements from b, and |a|-1 highest numbers from a. If the remainder is 2, then select all numbers from a, and |b|-1 highest numbers from b.

Once you have all the numbers, sort them in reverse order and concatenate. that is your answer.

Ultimately if n is the number of elements this algorithm returns a number that is al least n-1 digits long (except corner cases. see below).

NOTE: Take care of corner cases(i.e. what is |a|=0 or |b|=0 etc). (-1)%3 = 2 and (-2)%3 = 1 .

If m is the size of alphabet, and n is the number of elements, this my algorithm is O(m+n)

Beilul

Answer 5

Sorting the data is unnecessary, since there are only ten different values. Just count the number of zeroes, ones, twos etc. in O (n) if n digits are given. Calculate the sum of all digits, check whether the remainder modulo 3 is 0, 1 or 2.

If the remainder is 1: Remove the first of the following which is possible (one of these is guaranteed to be possible): 1, 4, 7, 2+2, 2+5, 5+5, 2+8, 5+8, 8+8.

If the remainder is 2: Remove the first of the following which is possible (one of these is guaranteed to be possible): 2, 5, 8, 1+1, 1+4, 4+4, 1+7, 4+7, 7+7.

If there are no digits left then the problem cannot be solved. Otherwise, the solution is created by concatenating 9's, 8's, 7's, and so on as many as are remaining.

(Sorting n digits would take O (n log n). Unless of course you sort by counting how often each digit occurs and generating the sorted result according to these numbers).

Respectively

Answer 6

Amit's answer has a tiny thing missing.

If bucket1 is not empty but it has a humongous value, lets say 79 and 97 and b2 is not empty as well and its 2 minimals are, say 2 and 5. Then in this case, when the modulus of the sum of all digits is 1, we should choose to remove 2 and 5 from bucket 2 instead of the minimal in bucket 1 to get the largest concatenated number.

Test case : 8 2 3 5 78 79

If we follow Amits and Steve's suggested method, largest number would be 878532 whereas the largest number possible divisble by 3 in this array is 879783

Solution would be to compare the appropriate bucket's smallest minimal with the concatenation of both the minimals of the other bucket and eliminate the smaller one.

Twelve