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

13
votes

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.

6
algorithmdynamic-programminggreedy
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 ? – ClemKeirua
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. – amit
@ClemKeirua : Yes, Brute Force is always an option. But i was hinking if it could be done in some efficient way. – user1599964
@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. – user1599964
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. – ClemKeirua

6 Answers

17
votes

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"
5
votes

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.

1
votes

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

1
votes

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)

0
votes

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).

0
votes

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.