找到一个数字集合中的最大子集，使得任意两个数字的和都不能被给定数字整除。

Question

我正在尝试解决Hackerrank问题非除数子集，如下所述：

我尝试了以下解决方案（对于示例测试用例有效）：

# The lines below are for Hackerrank submissions
# n, k = map(int, raw_input().strip().split(' '))
    # a = map(int, raw_input().strip().split(' '))

n = 4
k = 3
a = [1, 7, 2, 4]

while True:
    all_pairs = [(a[i],a[j]) for i in range(len(a)) for j in range(i+1,len(a))]
    tested_pairs = {pair: (pair[0] + pair[1]) % k != 0 for pair in all_pairs}
    disqualified_pairs = {key: value for key, value in tested_pairs.iteritems() if not value}.keys()
    if not disqualified_pairs:
        break
    occurrences = list(sum(disqualified_pairs, ()))
    counts = map(lambda x: occurrences.count(x), a)
    index_remove = counts.index(max(counts))
    a.remove(index_remove)

print len(a)

我试图识别“冲突”对，并删除出现最频繁的a元素，直到没有“冲突”对为止。

然而，大多数测试用例都会出现“运行时错误”。

可以假设上述算法在只需要删除一个数字（数字2）的简单情况下有效，但在更复杂的测试用例中失败。有人能看出问题出在哪里吗？

更新

根据poke的建议，测试k = 2和a = [1, 2, 3]，我做了以下修改：

n = 4
k = 2
a = [1, 2, 3]

while True:
    all_pairs = [(a[i],a[j]) for i in range(len(a)) for j in range(i+1,len(a))]
    disqualified_pairs = [pair for pair in all_pairs if (pair[0] + pair[1]) % k == 0]
    if not disqualified_pairs:
        break
    offending_numbers = sum(disqualified_pairs, ())   # 'Flatten' the disqualified pairs into a single list
    counts = {el: offending_numbers.count(el) for el in set(offending_numbers)}     # Count occurrences of each offending number
    number_to_remove = max(counts, key=counts.__getitem__)
    a.remove(number_to_remove)

print len(a)

得到的a是[2, 3]，包含两个元素，符合预期。我还检查了它是否仍适用于原始示例。但是，在某些测试用例中仍然会出现“分段错误”：

根据https://www.hackerrank.com/challenges/pairs/forum/comments/9154，分段错误通常是由于无效的内存访问（不存在的数组索引等）导致的。尽管如此，我仍然没有找到任何其他算法失败的测试用例。有什么想法吗？

- Kurt Peek

---

你可以考虑一些测试用例，以便对你的实现进行测试，这样怎么样？ - poke

我还没有想出任何解决方案。例如，我尝试了 a = [1, 7, 2, 4, 6, 3]，在这种情况下，算法似乎正确地删除了两个数字（2和3）。也许“运行时错误”与Hackerrank解决方案检查器有关？ - Kurt Peek

尝试使用 k = 2 和 a = [1, 2, 3]。 - poke

@Blender：说得好，我不知道。不过我之前在 Hackerrank 遇到过“超时”错误（因为使用了低效的算法），而这里并没有出现这种情况。 - Kurt Peek

@poke：感谢您提供这个“反例”，我想我知道问题出在哪里了。 - Kurt Peek

Answer 1

不需要生成所有的数对，而是可以通过计数模数来实现。

时间复杂度：O(n + k)

空间复杂度：O(k) 或 O(1)，因为k最大只有100，O(k) => O(1)

---

基本思路

(a + b) % k = ((a % k) + (b % k)) % k

由于(a % k)的范围在[0, k-1]之间，

(a % k) + (b % k)的范围在[0, 2k-2]之间

此外，

当(a % k) = 0且(b % k) = 0或者(a % k) + (b % k) = k时，(a + b) % k = 0

主要思想

1. 根据条件2，在选择任何模数i的值时，您可以选择除模数k-i之外的任何模数的值。
2. 在大多数情况下，选择模数i的多个值不会产生冲突。
3. 根据条件1，您最多只能从模0中选择1个值。
4. 当k为偶数时，k/2 + k/2 = k。当k为偶数时，您最多只能从模k/2中选择1个值。

---

根据以上信息，解决方案可能如下：

1. 如果n<2，则返回n。
2. 创建大小为k的数组Arr，所有初始值均为0，用于存储模数计数。
3. 循环遍历数组a，从索引i为0到n-1，将1添加到Arr [a [i]％k]中。
4. 将计数器初始化为0。
5. 循环遍历数组Arr，从索引i为1到k-(k/2)-1，将Max(Arr [i]，Arr [k-i])添加到计数器中。
6. 如果Arr [0]> 0，则将1添加到计数器中。
7. 如果k％2 = 0且Arr [k/2]> 0，则将1添加到计数器中。
8. 返回计数器。

- hk6279

Answer 2

我使用的方法是：

1. find power set of given list of integers.
2. sort power set by subset size.
3. iterate down the sorted power set and print if subset meets problem's conditions.

在Java中：

import java.util.*;
public class f implements Comparator<List<?>> {

    @Override
    public int compare(List<?> o1, List<?> o2) {
        return Integer.valueOf(o1.size()).compareTo(o2.size());
    }
    static ArrayList<ArrayList<Integer>> powerSet = new ArrayList<>();

    // get power set of arr
    static void g(int arr[],int[] numbers,int i){
        if(i==arr.length){
            ArrayList<Integer> tmp = new ArrayList<>();
            for(int j = 0;j<arr.length;j++){
                if(arr[j]==1) tmp.add(numbers[j]);
            }
            powerSet.add(tmp);
            return;
        }
        arr[i] = 1;
        g(arr,numbers,i+1);
        arr[i] = 0;
        g(arr,numbers,i+1);
    }
    static void h(int[] a){
        int[] arr=new int[a.length];
        for(int j =0;j<arr.length;j++){
            arr[j]=0;
        }
        g(arr,a,0);
    }
    // check whether the sum of any numbers in subset are not evenly divisible by k
    static boolean condition(ArrayList<Integer> set,int k){
        for(int i = 0;i<set.size();i++){
            for(int j = i+1;j<set.size();j++){
                if((set.get(i)+set.get(j))%k==0){
                    return false;
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int[] a = new int[n];
        for (int i=0;i<n;i++){
            a[i]=in.nextInt();
        }


        h(a);
        Collections.sort(powerSet, new f());
        for(int i=powerSet.size()-1;i>0;i--){
            if(condition(powerSet.get(i),k)){
                System.out.println(powerSet.get(i).size());
                break;
            }
        }

    }
}

结果： 测试用例#9的错误是由StackOverflowError引起的：

我不太熟悉hackerrank的错误，但也许你的错误类似。

- Bobas_Pett