Recent Tutorials and Articles
    HackerRank Solution: Non Divisible Subset
    Published on: 18th July 2016

    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.

    Published on: 18th July 2016

    Comment Form is loading comments...