hackerrank上的一道题——Non-Divisible Subset

题目描述

个人觉得比较难想诶

 如果i+j可以被k整除，那么i%k+j%k == 0或者k

利用这个性质可以将数按照取余的余数分割为k个数组，然后如果a[i]+a[j]==k，则比较a[i]和a[j]的长度，谁长选择哪一个添加到subset中，对于a[0]，如果大于0则result+1，如果k%2==0，则对于a[k/2]，如果大于0则result+1，具体代码如下：

import java.util.ArrayList;
import java.util.Scanner;

/**
 * Created by huliang on 16/7/25.
 */
public class Solution {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int[] a = new int[n];
        int[][] arr = new int[k][1];

        // 获取原始数据
        for (int i = 0; i < n; i++) {
           a[i] = scanner.nextInt();
            arr[a[i]%k][0]++;
        }
        int result = 0;
        if (arr[0][0] > 0) {
            result++;
        }
        for (int i = 1; i < k / 2 + 1; i++) {
            if (i == k - i) {
                result += 1;
           } else {
                int length1 = arr[i][0];
                int length2 = arr[k-i][0];
                result += Math.max(length1, length2);
            }
        }
        System.out.println(result);
    }
}