1

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.

6
  • Use LCM or HCF in mathematics...you say largest number, at the same time you are also saying need not use all numbers 😊 Jul 30, 2016 at 16:00
  • 1
    I'm voting to close this question as off-topic because it should probably be asked on math.stackexchange.com or programmers.stackexchange.com. Jul 30, 2016 at 16:02
  • Can a digit in the array be used more than once in the number?
    – Oriol
    Jul 30, 2016 at 16:14
  • @Oriol yes every number has frequency count, it can be used atmost that many times. Jul 30, 2016 at 16:37
  • "frequency count"? You should have mentioned that in your original post. Or is that what you meant by "array of digits"? I assumed (and most others, probably) that you meant some subset of {0,1,2,...,9}. But now it sounds like the array of digits could have repeats. It would help us immensely if you posted your best attempt at the problem.
    – Teepeemm
    Jul 30, 2016 at 19:42

1 Answer 1

2

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

3
  • 1
    Pretty much what I was going to say. The not divisible by threes get grouped into classes of mod 1 and mod 2 and paired off from highest to lowest. Should be pretty easy.
    – shawnt00
    Jul 30, 2016 at 16:47
  • @NPE assume set1[4,4,4] and set2[8,8,8] , initially length of both set is 3 ,then is the algorithm giving correct answer, I guess its wrong, as for first loop it takes 4 and 8 , then length of both gets to 2 and then it will break, rather we could have taken all elements from set2 i.e.[8,8,8] Jul 31, 2016 at 2:14
  • Don't you mean to check lengths as a multiple of three rather than equal to the and then only take three at a time? And you should take two pairs from (1) and (2) over a group of three but a group of three in favor of only one pair. I hadn't thought about this yesterday.
    – shawnt00
    Jul 31, 2016 at 15:01

Not the answer you're looking for? Browse other questions tagged or ask your own question.