数论 - 整除问题 --- 整数集合中找出3的最大倍数

Mean: 

 题目描述：给一个包含非负整数的数组(长度为n)，找出由这些数字组成的最大的3的倍数，没有的话则输出impossible。

analyse:

首先想到的就是直接暴力，这是最蠢的方法，数据一大的话，必会TLE。

直接用蛮力的话，生成所有的组合，为 2^n个，对每个数字再进行比较判断，需要 O(n)的时间，因为n可能会比较大，需要每个位的比较。

总的时间复杂度为O(n * 2^n). 

那么到底要怎么做呢？

首先我们来了解几个数学知识：

1)一个数n对m取余的余数为a1，b为n的每一位数字的和，那么有：n%m=b%m=a1。

　　例如，如果对于151和它的各位之和7，对于3的余数都为1。

2)一个数是3的倍数，则该数字各位总和为3的倍数。

　　例如，让我们考虑8760，它是3的倍数，因为数字总和为8 + 7 + 6 + 0 = 21，这是3的倍数。

　　推论：一个数是3的倍数，那么构成他的数字的排列为一个新的数字，这个数字仍然是3的倍数。

Time complexity：O(nlongn)

Source code：

 暴力代码：

　　

数学方法：