C#实现HackerRank Non-Divisible Subset逻辑错误排查求助

我在做HackerRank的「Non-Divisible Subset」练习题，题目要求：给定整数列表和数字k，输出列表中满足任意两数之和都不能被k整除的最大非重复整数子集的大小。

但我的代码运行结果不对，当输入k=9，列表为422346306, 940894801, 696810740, 862741861, 85835055, 313720373时，预期输出是5，我的代码输出却是6，找不到逻辑问题，求帮忙排查。

我的代码 #

public static int nonDivisibleSubset(int k, List<int> s)
{
    var x = GetPerm(s);

    var y = x.Where(x => x.Value % k != 0).Select(x=>x.Key).ToList();
    var a = y.SelectMany(x => x).ToHashSet();

    return a.Count();

}

static Dictionary<List<int>,int> GetPerm (List<int> list)
{
    Dictionary<List<int>,int> perm = new Dictionary<List<int>, int>();

    for (int i = 0; i < list.Count; i++)
    {
        for (int j = i+1; j < list.Count; j++)
        {
            List<int> sumCouple = new List<int>();
            sumCouple.Add(list[i]);
            sumCouple.Add(list[j]);
            perm.Add(sumCouple, sumCouple.Sum());
        }

    }
    return perm;
}

代码逻辑错误分析 #

你的思路完全偏离了题目要求：
现在的代码只是把所有“参与过和不被k整除的数对”的数字去重后统计数量，但这和题目要的一个子集里任意两数之和都不被k整除完全不是一回事。

举个例子，测试用例里肯定存在某两个数的和能被9整除，但你的代码把所有数都算进去了，所以输出6。但实际上必须去掉其中一个数，才能让剩下的5个数两两之和都不被9整除，这才是正确答案。

正确解法思路 #

核心靠余数的性质解决：

• 若两个数的余数相加等于k，它们的和就能被k整除
• 余数为0的数，只能和同样余数0的数冲突（0+0=0，能被k整除）
• 若k是偶数，余数为k/2的数也只能和自身冲突

具体步骤：

1. 统计每个数字对k取余后的余数出现次数
2. 余数0的情况：最多只能选1个
3. 遍历余数1到k/2：
   • 如果当前余数i和k-i相等（k是偶数且i=k/2），最多选1个
   • 否则选余数i和k-i中数量多的那一组，加到结果里

正确代码实现 #

public static int nonDivisibleSubset(int k, List<int> s)
{
    int[] remainderCounts = new int[k];
    foreach (int num in s)
    {
        int rem = num % k;
        remainderCounts[rem]++;
    }

    int result = 0;
    // 处理余数为0的数：最多选1个
    if (remainderCounts[0] > 0)
    {
        result = 1;
    }

    // 遍历1到k/2的余数
    for (int i = 1; i <= k / 2; i++)
    {
        if (i == k - i)
        {
            // k为偶数时，余数k/2的数最多选1个
            result += 1;
        }
        else
        {
            // 选两组余数中数量多的那一组
            result += Math.Max(remainderCounts[i], remainderCounts[k - i]);
        }
    }

    return result;
}

内容的提问来源于stack exchange，提问作者Diego