能被5和6整除的最大数

Question

我得到一个数字数组，其中元素的范围是0-9，我需要使用数字构造最大的数字，使得形成的数字可以被5和6整除。如何解决这个问题有效地使用更好的算法。它不需要使用所有提供的数字，但形成的数字应该是最大的并且可以被 5 和 6 整除。

Answer 1

tl;dr 这个问题本质上可以简化为找到数字之和能被三整除的最大数字子集。这可以在与位数成线性关系的时间内完成。

这可以使用 prime factorization and divisibility rules 来解决。

6的质因数分解为2*3。鉴于您还需要被 5 整除，这意味着您要形成一个可被 2、3 和 5 整除的数字。

我们可以像这样重组三个除数：2*5 和 3。换句话说，这个数必须能被 10 和 3 整除：

只有以零结尾的数字才能被 10 整除。 这意味着，从你的数字数组中，你需要留出一个零到满足这个整除要求。
只有数字总和为 3 的数字才能被 3 整除。 这意味着，从数组中的剩余数字中，您正在寻找总和可被三整除的最长子集（通过选择较大数字而不是较小数字来打破长度关系）。

一旦你有了数字，你就可以通过从大到小（零出现在末尾）对数字进行排序来形成数字。

因此，我们已将问题简化为寻找总和可被 3 整除的子集的问题。我们可以首先注意到所有本身可被三整除的数字（即零、3、6 和 9）可以而且应该始终 selected。

至于剩余的数字（个位、2、4、5、7 和 8），您正在查找 select 可被三整除的组（例如，1+2、2 +5+8 等）。如果我们将等于 1 mod 3 的数字表示为 ①，等于 2 mod 3 的数字表示为 ②，则形成此类组的唯一可能性是 ①+①+①、①+② 和 ②+② +②.

以下 Python 解决方案将所有这些想法结合在一起：

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

（要将其转化为线性时间解决方案，我们所要做的就是将 O(n logn) sorted() 调用替换为 counting sort。）

能被5和6整除的最大数

Largest number to form divisible by 5 and 6

math

numbers

division