Non-Divisible Subset

It is Saturday and the forecast calls for the sun to shine on and off during the day. I am planning on fixing a couple pizzas from scratch. After breakfast I made the dough. It will rest for at least two hours before I make and bake the pies. My wife and I should be having lunch around 01:00 PM; at least, that is the plan.

This morning I looked at the Non-Divisible Subset challenge from Hacker Rank. Tried a couple approaches but did not submit them because they were using brute force and figured that they would not pass. There had to be a simpler approach.

I then spent some time searching the web with Google. Some clever and better approaches were suggested. Allow me to describe the overall approach and then will see the solution.

By converting the requirements of this challenge from division to addition the approach is much simpler. Take a gander:

Two different numbers n1 and n2 are divisible by k if and only if:

(n1 % k) + (n2 % k) = k

We can verify this using some examples:

n1 = 10, n2 = 12, k = 3

The sum of these numbers is not divisible:

10 % 3 + 12 % 3 = 1 (NOT equal to k = 3)

Similarly,

n1 = 10, n2 = 11, k = 3

The sum of these numbers is divisible:

10 % 3 + 11 % 3 = 3 (EQUAL to k = 3)

There are some special conditions to note such as:

1. Remainders for some numbers are 0
2. Remainders for some 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 to avoid counting both.

I used the following test cases:

4 3
1 7 2 4

3

15 7
278 576 496 727 410 124 338 149 209 702 282 718 771 575 436

11


7 4
19 10 12 10 24 25 22

3


5 5
2 3 7 8 12

3


4 4 
0 5 7 10

3


13 5
1 2 3 4 5 6 7 8 9 10 11 12 13

7


5 3
2 3 4 5 6

3

The test scaffolding was provided by HackerRank in the main() method of the solution.

My solution follows:

	/*
	 * complete this function
	 */
    static int nonDivisibleSubset(int k, int[] S) {
    	
//    	// ???? ????
//    	System.out.println("k: " + k);
//    	System.out.print("S: ");
//    	for (int s : S)
//    		System.out.print(s + " ");
//    	System.out.println("\n");
    	
    	// **** declare and populate array of remainders ****
    	int[] remainderArr = new int[k];
    	
    	for (int n : S) {
    		
    		// ???? ????
    		System.out.println("n % k (" + n + " % " + k + "): " + n % k);
    		
    		remainderArr[n % k]++;
    	}
    	
    	// ???? ????
    	System.out.print("remainderArr: ");
    	for (int s : remainderArr)
    		System.out.print(s + " ");
    	System.out.println("\n");

    	// **** set initial number of elements in the subset ****
    	int zeroRemainder = remainderArr[0];
    	
    	// ???? ????
    	System.out.println("        zeroRemainder: " + zeroRemainder);
    	
    	// **** consider only one of the numbers ****
    	int numOfElementsInSubset = (zeroRemainder > 0) ? 1 : 0;
    	
    	// ???? ????
    	System.out.println("numOfElementsInSubset: " + numOfElementsInSubset + "\n");
    	 	
    	// **** ****
        for (int i = 1; i <= (k / 2); i++) {
        	
        	// ???? ????
        	System.out.println("i: " + i + " k - i: " + (k - i));
        	
        	// **** ****
            if (i != k - i) {
                numOfElementsInSubset += Math.max(remainderArr[i], remainderArr[k - i]);
            } else {
                numOfElementsInSubset++;
            }

            // ???? ????
            System.out.println("numOfElementsInSubset: " + numOfElementsInSubset);
        }
        
        // **** return the number of elements in the subset ****
        return numOfElementsInSubset;
    }

Note that I added some code to display intermediate values in order to test and debug the code.

If you are interested in the full solution you can find it in my GitHub repository ().

If you have issues with this or any other post in this blog, or if you need some help with any phase in the SDLC of a project, please leave me a note bellow. Requests will not be made public.

Keep on reading and experimenting. It is the best way to learn.

John
Follow me on Twitter:  @john_canessa

PS:  Tomorrow morning will download and experiment with TensorFlow 2.0 for a few hours. Looking forward to see how Google has improved the interface to it. Hopefully will have time to generate a post.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.