[hackerrank][python][c++] non-divisible-subset

連結: https://www.hackerrank.com/challenges/non-divisible-subset/problem

這題如果看敘述，一定會被騙到去列排列組合，然後在兩兩相加除 k，嗚嗚

看了一下解答，這題應該是沒其他更好的解了:

def nonDivisibleSubset(k, s):
    res = [0 for i in range (0, k)]
    for i in s:
        res[i%k] += 1
    maxN = 1 if res[0]>0 else 0
    for i in range(1, k//2+1):
        if (i != k-i):
            maxN += max(res[i], res[k-i])
        elif res[i] != 0:
            maxN += 1
    return maxN

概念上就是先建立餘數表，互補的餘數不能同時加到 ans set，所以只能取大的來當作答案

然後比較特別的地方是:

1. 整除的數只能加一個到 ans set，加兩個就會出現可以整除的數對
2. 如果除數是偶數，最中間的兩組會互補，所以如果有出現這種餘數，只能加一個到 ans set 中

同場加映 C++ 的解(一年沒寫 C++ 啦，真的快忘光光了):

int nonDivisibleSubset(int k, vector<int> s) {
    vector<int> rems(k);
    int answer = 0;
    // counting input numbers based on their remainders
    for (int i = 0; i < s.length(); i++)
        rems[s[i]%k]++;
        
    // comparing pairs of remainders so that r1 + r2 = k,
    // and adding up the "population" of the most frequent one
    for(int i = 0; i < (k-1)/2; i++)
        answer += max(rems[i+1], rems[k-1-i]); 
        
    // +1 if tmp%k == 0, and +1 if tmp%k/2 == 0
    answer += (rems[0] > 0) + (k%2 == 0 && rems[k/2] > 0);
    return answer;
}