https://www.hackerrank.com/challenges/non-divisible-subset
https://www.martinkysel.com/hackerrank-non-divisible-subset-solution/
https://www.martinkysel.com/hackerrank-non-divisible-subset-solution/
public static void main(String[] args) {
final Scanner in = new Scanner(System.in);
final int n = in.nextInt();
final int k = in.nextInt();
// Idea is to divide all numbers of set by k and put these to a Map with:
// - key as remainder of input number and k
// - value as count of input numbers having remainder same as key
// If we have numbers with remainders as 0 then we will consider only one of those as
// subset with one number complies with subset criteria.
final Map<Integer, Integer> remainders = new HashMap<>();
for(int i = 0; i < n; i++) {
int remainder = in.nextInt() % k;
remainders.compute(remainder, (key, value) -> (value == null || key == 0) ? 1 : (value + 1));
}
// Iterate through all the unique pair of combinations for k and take maximum of numbers count
// having remainder same as numbers in combination pair.
// E.g. 5 has unique combinations - (1,4),(2,3). We will take maximum count out of 1 and 4 and
// similarly out of 2 and 3. We will consider one number out of 0 remainders if any.
int noOfElementsInSubset = remainders.getOrDefault(0, 0);
int i = 1;
for(; 2 * i < k; i++) {
noOfElementsInSubset += Math.max(remainders.getOrDefault(i, 0), remainders.getOrDefault(k - i, 0));
}
// For even numbers, we will have combination having same numbers. E.g. 6 will have a combination - (3,3).
// For this, we will just consider only one number.
if(2 * i == k) {
noOfElementsInSubset++;
}
System.out.println(noOfElementsInSubset);
in.close();
}
Given a set, , of distinct integers, print the size of a maximal subset, , of where the sum of any numbers in is not evenly divisible by .
Input Format
The first line contains space-separated integers, and , respectively.
The second line contains space-separated integers (we'll refer to the value as ) describing the unique values of the set.
The second line contains space-separated integers (we'll refer to the value as ) describing the unique values of the set.
Constraints
- All of the given numbers are distinct.
Output Format
Print the size of the largest possible subset ().
Sample Input
4 3
1 7 2 4
Sample Output
3
Explanation
The largest possible subset of integers is , because no two integers will have a sum that is evenly divisible by :
- , and is not evenly divisible by .
- , and is not evenly divisible by .
- , and is not evenly divisible by .
The number cannot be included in our subset because it will produce an integer that is evenly divisible by when summed with any of the other integers in our set:
- , and .
- , and .
- , and .
Thus, we print the length of on a new line, which is .
https://www.martinkysel.com/hackerrank-non-divisible-subset-solution/
https://www.martinkysel.com/hackerrank-non-divisible-subset-solution/
This is by all means not an easy task and is also reflected by the high failure ratio of the participants. For a sum of two numbers to be evenly divisible by k the following condition has to hold. If the remainder of N1%k == r then N2%k = k-r for N1+N2 % k == 0. Let us calculate the set of all numbers with a remainder of r and k-r and pick the larger set. If the remainder is half of k such as 2 % 4 = 2 or exactly k such as 4 % 4 = 0, just one number from each of these sets can be contained in S’.
idea就是：要使子集中任意两个数之和不能被k整除，等价于任意两个数被k除的余数之和不能被k整除。而所有余数的可能是比较少的，即0, 1, ..., k-1。用一个Hash统计每个余数出现的次数。
如果k=1，那么集合内所有数都能被k整除，子集最多只能有一个数；
然后用贪心的方法选择i和(k-i)出现次数较多的，需要提醒的是，对
0和 k/2这两个余数要特殊处理，对k/2还要做奇偶判断。 int n, k;
vector<int> a;
vector<int> cnt;
void load() {
cin >> n >> k;
a = vector<int>(n);
cnt = vector<int>(100, 0);
for (int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
a[i] %= k;
cnt[a[i]]++;
}
}
int solve() {
int rst = 0;
if (k == 1) {
return 1;
}
if (cnt[0] > 0) rst++;
for (int i = 1; i < k / 2; ++i) {
rst += max(cnt[i], cnt[k-i]);
}
if (k % 2 == 0) rst += (cnt[k/2]? 1:0);
else rst += max(cnt[k/2], cnt[k/2+1]);
return rst;
}
};