## Generate maximum number from array of digits which is divisible by 2, 3 and 5

Whoa! Blogging 2 questions in one day! I guess I am actually in the mood to write tonight! Lets get started.

Let us take an example array, {9, 6, 3, 4}

So how should we go about solving for this example? **Well, you don’t!** Because if you notice, apart from 3, we are looking for divisibility by both 2 and 5. Which means that the final number should end in a “0”. And this array does not have a zero!

Moving on, here is the new array, {9, 6, 3, 4, 0}

Now what? Divisibility of 3 means that the sum of digits of the number should be divisible by 3. **Note that you don’t have to use up all of the digits.** So what do you do?

You can either go for an **exponential approach by forming the power set of the array** and shortlist the ones which have a sum divisible by 3 and then go on to see which of these has the most number of digits and even then if you have a tie, you’ll go for the one with the biggest digit.. and so on. **But wait… I thought we were smart! Then why do all this?!**

You can **instead** do the following –

1. Check if the array has atleast one 0 (zero). If not, we can’t form a number. Go back to bed.

2. Since you are still awake, go on to sort the array in descending order.

3. Now sum up the digits (and keep repeating Steps 3-6 till sum>=3). If your sum%3 == 0, we are done! This sequence is the biggest number. Sleep peacefully.

4. If not, there are 2 possibilities, sum%3 = 1 or 2 (let us call this remainder “R” which can have value 1 or 2)

5. We’ll first try to remove a number from this array which satisfies number%3==R starting from the smallest number in the array. As soon as you find such a number, remove it!

6. If not (life is such), go on to remove 2 numbers starting from the smallest number such that numbers%3==(3-R). Once you have removed 2 such numbers, you might have your desired number! Loop back to Step 3 and check the sum!

7. In the end you might be left with an array with only a 0. In that case your answer is either Aryabhata’s creation or “Cannot be formed” depending on the question’s requirement.

To quickly run through the example, {9, 6, 3, 4, 0}

In descending order, this is, {9, 6, 4, 3, 0} which sums to 22

22%3 = 1

Hence start trying to find a number%3=1 from the smallest,

3%3 = 1? No!

4%3 = 1? Yes!

Remove 4 and we are left with {9,6,3,0} or 9630 –> *Which is the panacea for our metaphorical insomnia*! Have fun! 🙂