This tutorial provides Java solution to "Non divisible subset" challenge of HackerRank.
Hackerrank Challenge Details
Problem Statement:
Given a set, S, of n integers, print the size of a maximal subset, S', of S where the sum of any 2 numbers in S' arenot evenly divisible by k.
Input Format:
The first line contains 2 space-separated integers, n and k, respectively.
The second line contains n space-separated integers (we'll refer to the ith value as ai) describing the unique values of the set.
Output Format:
Print the size of the largest possible subset (S').
Constraints:
- 1 < n < 106
- 1 < k < 100
- 1 < ai < 109
- All of the given numbers are distinct.
Sample Input:
4 3
1 7 2 4
Sample Output:
3
Explanation:
The largest possible subset of integers is S' = {1, 7, 4}, because no two integers will have a sum that is evenly divisible by k = 3:
- 1 + 7 = 8, and 8 is not evenly divisible by 3.
- 1 + 4 = 5, and 5 is not evenly divisible by 3.
- 7 + 4 = 11, and 11 is not evenly divisible by 3.
The number 2 cannot be included in our subset because it will produce an integer that is evenly divisible by k = 3 when summed with any of the other integers in our set:
- 1 + 2 = 3, and 3/3 = 1 (remainder = 0).
- 4 + 2 = 6, and 6/3 = 2 (remainder = 0).
- 7 + 2 = 9, and 9/3 = 3 (remainder = 0).
Thus, we print the length of S' on a new line, which is 3.
Solution Details
Java Implementation:
package com.saintech.allprogtutorials.hackerrank.algos;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
/**
* @author Sain Technology Solutions
*
* Solution to Problem - https://www.hackerrank.com/challenges/non-divisible-subset
*
*/
public class NonDivisibleSubset {
/**
* We will convert this problem to addition from division as handling addition is much easier. We can easily observe that
* sum of two number can only be divisible by k if remainder of these numbers in division to k adds to k. In other words,
* two numbers n1 and n2 are divisible by k if and only if -
* (n1 % k) + (n2 % k) = k
*
* We can easily verify this using some examples:
* E.g. n1 = 10, n2 = 12, k = 3. Sum of these numbers is not divisible as 10 % 3 + 12 % 3 = 1 (not equal to k = 3).
* Similarly, n1 = 10, n2 = 11, k = 3. Sum of these numbers is divisible as 10 % 3 + 11 % 3 = 3 (equal to k = 3).
*
* There are also some special conditions such as -
* 1. Remainders for many numbers are 0
* 2. Remainders for many numbers are equal to k/2 (only applicable for even values of k)
* In both the above cases, we will consider only one of the numbers falling into one of above conditions.
*
* @param args containing command line arguments.
*/
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();
}
}
Thank you for reading through the tutorial. In case of any feedback/questions/concerns, you can communicate same to us through your comments and we shall get back to you as soon as possible.