數論 - 整除問題 --- 整數集合中找出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：

 暴力代碼：

　　

數學方法：