HackerRank Non-Divisible Subset(Algorithms>Implementation)

題目:
給定一個由n個不同integer所成之集合S，
印出最大的子集合S'，當中S'必須符合以下條件:
S'中任意2元素之和無法被k所整除。

輸入:
第一行分別給入n, k，用空格隔開。
第二行給入n個數字，代表這個集合的所有元素。

輸出:
印出符合前述之最大可能的子集合S'的大小。

範例輸入:

4 3
1 7 2 4

輸出則為

3

解題:
思路請參照
http://cs.stackexchange.com/questions/57873/maximum-subset-pairwise-not-divisible-by-k

簡單來說，2個數的和能被k整除的話，
代表它們除以k的餘數和也能被k整除(同餘定理)。
舉例來說:
a = bk + c, d = ek + f
a+d = k(b+d) + c+f
前項當然能被k整除，那麼a+d能不能被k整除，
就要看c+f能不能被k整除。

知道這點的話，那麼除以k的餘數可能為0~k-1，
我們可以先分類記錄成一個陣列，
用來表示除以k的餘數為s_i的話，
num[s_i]有幾個。

當k是奇數的時候，兩個數要加起來能被k整除的話，
必然是一個比k/2小，一個比k/2大。
於是遍歷從1到比k/2小的整數，
for(int i = 1; i < k/2; i++)
檢查是num[i]比較大呢，還是num[k-i]比較大呢?
因為兩個互斥，我們就取比較大的放入S'中。

接著留意k是偶數的時候，由於餘數是k/2的話，
兩個一配起來就可以被k整除了，
所以在num[k/2]>0的狀況仍然只能取1個進S'中。
同樣的，餘數是0的狀況下也只能取1個進S'中。

由於在計算時k/2比較特殊，下面的code中有特別分開來計算，
請參閱下方的code。

另外特殊的case為n只有1個或k剛好是1的狀況，
這時候就只能取1個了!

這題在從頭仔細思考過一遍以後，
其實並不算太過複雜，
根本核心在於同餘的概念，
以及如何處理k/2的case。
難怪雖然是Easy Level，答對率卻並不是太高。

Code：

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main() {
    int n, k, result=0;
    scanf("%d %d",&n, &k);
    // Special case: 1. integer num only 1 -> result = 1; 
    //               2. divisor k = 1 -> result = 1
    if(n == 1 || k == 1){
        printf("%d", 1);
    }else{    
        int s_i, num[k];
        for(int i = 0; i < k; i++) 
            num[i] = 0;
        // Store num of those whose remainder is k' at num[k'].
        for(int arr_i = 0; arr_i < n; arr_i++){
           scanf("%d",&s_i);
           s_i %= k;
           num[s_i] += 1;
        }

        for(int i = 1; i < k/2; i++){
            if(num[i] > num[k-i])
                result += num[i];
            else
                result += num[k-i];
        }
        if(num[0] > 0) result++;
        if(k % 2 == 0){ 
            if(num[k/2] > 0)
                result++;
        }else{
            if(num[k/2] > num[k/2 + 1])
                result += num[k/2];
            else
                result += num[k/2 +1];
        } 
        printf("%d", result);
    }           
    
    return 0;
}