I am given an array of digits, where elements are ranging from 0-9, I need to construct the largest number using the digits such that the number formed is divisible by both 5 and 6. How to solve this problem effectively using better algorithm. It's not required to use all the digits provided but number formed should be largest and divisible by both 5 and 6.
tl;dr The problem can essentially be reduced to that of finding the largest subset of digits whose sum is divisible by three. This can be done in time that is linear in the number of digits.
This can be tackled using prime factorization and divisibility rules.
The prime factorization of 6 is 2*3. Given that you also need divisibility by 5, this means that you're looking to form a number that's divisible by 2, 3 and 5.
We can regroup the three divisors like so: 2*5 and 3. In other words, the number has to be divisible by 10 and 3:
Only numbers that end in zero can be divisible by 10. This means that, from your array of digits, you need to set aside a zero to satisfy this divisibility requirement.
Only numbers whose digits sum up to three are divisible by 3. This means that, from the remaining digits in your array, you're looking for the longest subset whose sum is divisible by three (breaking length ties by choosing larger digits over smaller ones).
Once you have the digits, you can form the number by sorting the digits from the largest to the smallest (with the zero appearing at the end).
We have thus reduced the problem to that of finding subsets whose sums are divisible by three. We can start by noting that all digits that are themselves divisible by three (i.e. the zeroes, 3s, 6s and 9s) can and should always be selected.
As to the remaining digits (the ones, 2s, 4s, 5s, 7s and 8s), you're looking to select groups that are divisible by three (for example, 1+2, 2+5+8 etc). If we denote digits that equal 1 mod 3 as ① and digits that equal 2 mod 3 as ②, the only possibilities for forming such groups are ①+①+①, ①+② and ②+②+②.
The following Python solution puts all these ideas together:
def get_n_mod_3(digits, n):
return sorted(d for d in digits if d % 3 == n)
def solve(digits):
# select all (0 mod 3)
selected = get_n_mod_3(digits, 0)
if not selected or selected[0] != 0:
# not divisible by both 2 and 5
return None
# select all (1 mod 3) and (2 mod 3)
set1 = get_n_mod_3(digits, 1)
set2 = get_n_mod_3(digits, 2)
while True:
# to simplify what follows, store the longer set in set1
# and the shorter in set2
if len(set1) < len(set2):
set1, set2 = set2, set1
if len(set1) == 3 and len(set2) < 2:
selected.extend(set1)
break
elif set1 and set2:
selected.append(set1.pop())
selected.append(set2.pop())
elif len(set1) < 3:
break
return ''.join(map(str, sorted(selected, reverse=True)))
print solve([1, 4, 2, 2, 9, 0, 2, 1, 5, 5, 7, 2, 0, 8, 1, 1, 8])
(To turn this into a linear-time solution, all we have to do is replace the O(n logn) sorted() call with counting sort.)