# Non-Divisible Subset

!!! UPDATE !!!

What called my attention was a comment which I will respond to as soon as I finish updating the contents of this post.

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.

```Microsoft Windows [Version 10.0.18363.836]

C:\Users\johnc>dir
Volume in drive C is OS
Volume Serial Number is D4DF-7908

Directory of C:\Users\johnc

05/29/2020  03:46 PM    <DIR>          .
05/29/2020  03:46 PM    <DIR>          ..
05/13/2020  03:07 PM                57 .angular-config.json
06/04/2020  04:54 PM    <DIR>          .atom
05/13/2020  03:03 PM    <DIR>          .config
09/22/2019  08:00 AM    <DIR>          .eclipse
03/15/2020  08:38 AM                59 .gitconfig
04/23/2020  11:11 AM    <DIR>          .p2
05/07/2020  08:11 AM         1,005,502 .pipwin
04/21/2020  08:07 AM    <DIR>          .pylint.d
09/22/2019  08:00 AM    <DIR>          .tooling
03/10/2020  03:53 PM    <DIR>          .vscode
05/13/2020  07:59 AM    <DIR>          3D Objects
05/13/2020  07:59 AM    <DIR>          Contacts
04/08/2020  07:59 AM    <DIR>          ContainsCloseNums
02/17/2020  03:52 PM    <DIR>          Documents
09/22/2019  07:57 AM    <DIR>          eclipse
09/22/2019  07:59 AM    <DIR>          eclipse-workspace_0
05/13/2020  07:59 AM    <DIR>          Favorites
05/13/2020  07:59 AM    <DIR>          Music
05/13/2020  03:49 PM    <DIR>          my-app
09/12/2019  04:36 PM    <DIR>          NCH Software Suite
06/07/2020  07:42 AM    <DIR>          OneDrive
05/04/2020  03:42 PM    <DIR>          pipwin
05/13/2020  07:59 AM    <DIR>          Saved Games
05/13/2020  07:59 AM    <DIR>          Searches
05/11/2020  03:04 PM    <DIR>          source
05/13/2020  07:59 AM    <DIR>          Videos
05/05/2020  01:30 PM    <DIR>          vimfiles
05/27/2020  01:51 PM    <DIR>          workspace0
05/05/2020  01:51 PM             3,281 _viminfo
4 File(s)      1,008,899 bytes
29 Dir(s)  1,886,217,375,744 bytes free

C:\Users\johnc>cd workspace0

C:\Users\johnc\workspace0>dir
Volume in drive C is OS
Volume Serial Number is D4DF-7908

Directory of C:\Users\johnc\workspace0

05/27/2020  01:51 PM    <DIR>          .
05/27/2020  01:51 PM    <DIR>          ..
04/01/2020  08:57 AM    <DIR>          BST-Search
04/27/2020  08:46 AM    <DIR>          ClassesInPython
05/21/2020  02:24 PM    <DIR>          ComponentsInAGraph
04/10/2020  11:34 AM    <DIR>          ComposeRanges
04/08/2020  08:04 AM    <DIR>          ContainsCloseNums
05/08/2020  12:01 PM    <DIR>          CS50Python
05/27/2020  01:53 PM    <DIR>          CS50Uncertainty
05/19/2020  08:02 AM    <DIR>          DisjointSet
05/07/2020  02:44 PM    <DIR>          DownToZeroII
04/05/2020  08:32 AM    <DIR>          GraphBFS
05/26/2020  02:15 PM    <DIR>          JavaScriptEssential
04/21/2020  07:46 AM    <DIR>          Knights
04/24/2020  08:33 AM    <DIR>          Minesweeper
04/17/2020  03:41 PM    <DIR>          MissingNumber
03/29/2020  08:30 AM    <DIR>          ORCost
04/23/2020  11:13 AM    <DIR>          Python-Tutorial-CS50
04/22/2020  04:37 PM    <DIR>          PythonTutorial
04/19/2020  07:46 AM    <DIR>          RobotInAGrid
03/10/2020  04:24 PM    <DIR>          SortOnFrequency
04/29/2020  02:47 PM    <DIR>          UsingWithPython
04/28/2020  02:52 PM    <DIR>          WorkingWithFiles
0 File(s)              0 bytes
23 Dir(s)  1,886,217,441,280 bytes free

C:\Users\johnc\workspace0>git clone https://github.com/JohnCanessa/NonDivisibleSubset.git
Cloning into 'NonDivisibleSubset'...
remote: Enumerating objects: 6, done.
remote: Counting objects: 100% (6/6), done.
remote: Compressing objects: 100% (5/5), done.
remote: Total 6 (delta 0), reused 0 (delta 0), pack-reused 0
Unpacking objects: 100% (6/6), 2.58 KiB | 10.00 KiB/s, done.

C:\Users\johnc\workspace0>dir
Volume in drive C is OS
Volume Serial Number is D4DF-7908

Directory of C:\Users\johnc\workspace0

06/07/2020  08:06 AM    <DIR>          .
06/07/2020  08:06 AM    <DIR>          ..
04/01/2020  08:57 AM    <DIR>          BST-Search
04/27/2020  08:46 AM    <DIR>          ClassesInPython
05/21/2020  02:24 PM    <DIR>          ComponentsInAGraph
04/10/2020  11:34 AM    <DIR>          ComposeRanges
04/08/2020  08:04 AM    <DIR>          ContainsCloseNums
05/08/2020  12:01 PM    <DIR>          CS50Python
05/27/2020  01:53 PM    <DIR>          CS50Uncertainty
05/19/2020  08:02 AM    <DIR>          DisjointSet
05/07/2020  02:44 PM    <DIR>          DownToZeroII
04/05/2020  08:32 AM    <DIR>          GraphBFS
05/26/2020  02:15 PM    <DIR>          JavaScriptEssential
04/21/2020  07:46 AM    <DIR>          Knights
04/24/2020  08:33 AM    <DIR>          Minesweeper
04/17/2020  03:41 PM    <DIR>          MissingNumber
06/07/2020  08:06 AM    <DIR>          NonDivisibleSubset
03/29/2020  08:30 AM    <DIR>          ORCost
04/23/2020  11:13 AM    <DIR>          Python-Tutorial-CS50
04/22/2020  04:37 PM    <DIR>          PythonTutorial
04/19/2020  07:46 AM    <DIR>          RobotInAGrid
03/10/2020  04:24 PM    <DIR>          SortOnFrequency
04/29/2020  02:47 PM    <DIR>          UsingWithPython
04/28/2020  02:52 PM    <DIR>          WorkingWithFiles
0 File(s)              0 bytes
24 Dir(s)  1,886,216,470,528 bytes free

C:\Users\johnc\workspace0>cd NonDivisibleSubset

C:\Users\johnc\workspace0\NonDivisibleSubset>dir
Volume in drive C is OS
Volume Serial Number is D4DF-7908

Directory of C:\Users\johnc\workspace0\NonDivisibleSubset

06/07/2020  08:06 AM    <DIR>          .
06/07/2020  08:06 AM    <DIR>          ..
06/07/2020  08:06 AM             2,962 Solution.java
2 File(s)          3,584 bytes
2 Dir(s)  1,886,216,458,240 bytes free

# NonDivisableSubset
HackerRank problem solved last year, but forgot to post.

Forgot to create and obviously push my Java code to GitHub.
Doing so to address a question from a subscriber to my blog.

If interested the link to the problem in HackerRang follows:

https://www.hackerrank.com/challenges/non-divisible-subset/problem

My post describing my solution can be found using the following link:

Non-Divisible Subset

Will be updating the code and responding to the question today.

Enjoy;

John
```

The previous scree capture illustrates the steps I took to clone the new repository which I missed to create a year ago.

I used three test cases. The first follows:

```4 3
1 7 2 4

main <<< n: 4 k: 3
nonDivisibleSubset <<< k: 3
nonDivisibleSubset <<< S: 1 7 2 4 nonDivisibleSubset <<< n % k = (1 % 3): 1
nonDivisibleSubset <<< n % k = (7 % 3): 1
nonDivisibleSubset <<< n % k = (2 % 3): 2
nonDivisibleSubset <<< n % k = (4 % 3): 1
nonDivisibleSubset <<< remainderArr: 0 3 1  sum: 4 == n: 4
nonDivisibleSubset <<< zeroRemainder: 0
nonDivisibleSubset <<< numOfElementsInSubset: 0
nonDivisibleSubset <<< i: 1 k - i: 2
nonDivisibleSubset <<< max(3, 1)
nonDivisibleSubset <<< numOfElementsInSubset: 3
3
```

The second test case follows:

```7 4
19 10 12 10 24 25 22

main <<< n: 7 k: 4
nonDivisibleSubset <<< k: 4
nonDivisibleSubset <<< S: 19 10 12 10 24 25 22 nonDivisibleSubset <<< n % k = (19 % 4): 3
nonDivisibleSubset <<< n % k = (10 % 4): 2
nonDivisibleSubset <<< n % k = (12 % 4): 0
nonDivisibleSubset <<< n % k = (10 % 4): 2
nonDivisibleSubset <<< n % k = (24 % 4): 0
nonDivisibleSubset <<< n % k = (25 % 4): 1
nonDivisibleSubset <<< n % k = (22 % 4): 2
nonDivisibleSubset <<< remainderArr: 2 1 3 1  sum: 7 == n: 7
nonDivisibleSubset <<< zeroRemainder: 2
nonDivisibleSubset <<< numOfElementsInSubset: 1
nonDivisibleSubset <<< i: 1 k - i: 3
nonDivisibleSubset <<< max(1, 1)
nonDivisibleSubset <<< numOfElementsInSubset: 2
nonDivisibleSubset <<< i: 2 k - i: 2
nonDivisibleSubset <<< numOfElementsInSubset++
nonDivisibleSubset <<< numOfElementsInSubset: 3
3
```

The third and final test case follows:

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

main <<< n: 15 k: 7
nonDivisibleSubset <<< k: 7
nonDivisibleSubset <<< S: 278 576 496 727 410 124 338 149 209 702 282 718 771 575 436 nonDivisibleSubset <<< n % k = (278 % 7): 5
nonDivisibleSubset <<< n % k = (576 % 7): 2
nonDivisibleSubset <<< n % k = (496 % 7): 6
nonDivisibleSubset <<< n % k = (727 % 7): 6
nonDivisibleSubset <<< n % k = (410 % 7): 4
nonDivisibleSubset <<< n % k = (124 % 7): 5
nonDivisibleSubset <<< n % k = (338 % 7): 2
nonDivisibleSubset <<< n % k = (149 % 7): 2
nonDivisibleSubset <<< n % k = (209 % 7): 6
nonDivisibleSubset <<< n % k = (702 % 7): 2
nonDivisibleSubset <<< n % k = (282 % 7): 2
nonDivisibleSubset <<< n % k = (718 % 7): 4
nonDivisibleSubset <<< n % k = (771 % 7): 1
nonDivisibleSubset <<< n % k = (575 % 7): 1
nonDivisibleSubset <<< n % k = (436 % 7): 2
nonDivisibleSubset <<< remainderArr: 0 2 6 0 2 2 3  sum: 15 == n: 15

1 2 3 4 5 6  <== indices into array (lines NOT generated by the code)
^         ^
+---------+ 1 & 6
^     ^
+-----+   2 & 5
^ ^
+-+     3 & 4

nonDivisibleSubset <<< zeroRemainder: 0
nonDivisibleSubset <<< numOfElementsInSubset: 0

nonDivisibleSubset <<< i: 1 k - i: 6                <===
nonDivisibleSubset <<< max(2, 3)
nonDivisibleSubset <<< numOfElementsInSubset: 3

nonDivisibleSubset <<< i: 2 k - i: 5                <===
nonDivisibleSubset <<< max(6, 2)
nonDivisibleSubset <<< numOfElementsInSubset: 9

nonDivisibleSubset <<< i: 3 k - i: 4                <===
nonDivisibleSubset <<< max(0, 2)
nonDivisibleSubset <<< numOfElementsInSubset: 11

11
```

Note that I have manually added some comments in order to better explain what the code is doing. The reason for it is due to a comment I received.

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

```    // **** open scanner ****
private static final Scanner scanner = new Scanner(System.in);

/**
* test scaffolding
*/
public static void main(String[] args) throws IOException {

// **** open buffered writter ****
BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));

String[] nk = scanner.nextLine().split(" ");

int n = Integer.parseInt(nk[0]);

int k = Integer.parseInt(nk[1]);

// ???? ????
System.out.println("main <<< n: " + n + " k: " + k);

int[] S = new int[n];

String[] SItems = scanner.nextLine().split(" ");
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

for (int i = 0; i < n; i++) {
int SItem = Integer.parseInt(SItems[i]);
S[i] = SItem;
}

// **** compute the result ****
int result = nonDivisibleSubset(k, S);

// **** display the result ****
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();

// **** close buffered writer ****
bufferedWriter.close();

// **** close scanner ****
scanner.close();
}
```

My solution follows:

```	/**
* complete this function
*/
static int nonDivisibleSubset(int k, int[] S) {

// ???? ????
System.out.println("nonDivisibleSubset <<< k: " + k);
System.out.print("nonDivisibleSubset <<< S: ");
for (int s : S)
System.out.print(s + " ");

// **** declare array of remainders ****
int[] remainderArr = new int[k];

// **** populate the array of remainders ****
for (int n : S) {

// ???? ????
System.out.println("nonDivisibleSubset <<< n % k = (" + n + " % " + k + "): " + n % k);

remainderArr[n % k]++;
}

// ???? display the contents of the array ????
System.out.print("nonDivisibleSubset <<< remainderArr: ");
for (int s : remainderArr)
System.out.print(s + " ");

// ???? compute the sum of the array of remainders ????
int sum = IntStream.of(remainderArr).sum();
System.out.println(" sum: " + sum + " == n: " + S.length);

// **** set initial number of elements in the subset ****
int zeroRemainder = remainderArr[0];

// ???? ????
System.out.println("nonDivisibleSubset <<< zeroRemainder: " + zeroRemainder); // **** consider only one of the numbers **** int numOfElementsInSubset = (zeroRemainder > 0) ? 1 : 0;

// ???? ????
System.out.println("nonDivisibleSubset <<< numOfElementsInSubset: " + numOfElementsInSubset);

// **** loop moving from both ends inwards computing the elements in the subset ****
for (int i = 1; i <= (k / 2); i++) {

// ???? ????
System.out.println("nonDivisibleSubset <<< i: " + i + " k - i: " + (k - i));

// **** ****
if (i != (k - i)) {

// ???? ????
System.out.println("nonDivisibleSubset <<< max(" + remainderArr[1] + ", " + remainderArr[k - 1] + ")");

// **** ****
numOfElementsInSubset += Math.max(remainderArr[i], remainderArr[k - i]);
} else {

// ???? ????
System.out.println("nonDivisibleSubset <<< numOfElementsInSubset++");

// **** ****
numOfElementsInSubset++;
}

// ???? ????
System.out.println("nonDivisibleSubset <<< 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.

Following are the commands I issued to post the code:

```# **** ****
C:\Users\johnc\workspace0\NonDivisibleSubset>git status
On branch master
Your branch is up to date with 'origin/master'.

Changes not staged for commit:
(use "git add <file>..." to update what will be committed)
(use "git restore <file>..." to discard changes in working directory)
modified:   Solution.java

no changes added to commit (use "git add" and/or "git commit -a")

# **** ****

# **** ****
C:\Users\johnc\workspace0\NonDivisibleSubset>git status
On branch master
Your branch is up to date with 'origin/master'.

Changes to be committed:
(use "git restore --staged <file>..." to unstage)
modified:   Solution.java

# **** ****
1 file changed, 50 insertions(+), 31 deletions(-)

# **** ****
C:\Users\johnc\workspace0\NonDivisibleSubset>git status
On branch master
(use "git push" to publish your local commits)

nothing to commit, working tree clean

# **** ****
C:\Users\johnc\workspace0\NonDivisibleSubset>git push origin master
Enumerating objects: 5, done.
Counting objects: 100% (5/5), done.
Delta compression using up to 12 threads
Compressing objects: 100% (3/3), done.
Writing objects: 100% (3/3), 918 bytes | 918.00 KiB/s, done.
Total 3 (delta 1), reused 0 (delta 0)
remote: Resolving deltas: 100% (1/1), completed with 1 local object.
To https://github.com/JohnCanessa/NonDivisibleSubset.git

# **** ****
C:\Users\johnc\workspace0\NonDivisibleSubset>git status
On branch master
Your branch is up to date with 'origin/master'.

nothing to commit, working tree clean

# **** ****
C:\Users\johnc\workspace0\NonDivisibleSubset>git log
Author: JohnCanessa <john.canessa@gmail.com>
Date:   Sun Jun 7 10:39:13 2020 -0500

Date:   Sun Jun 7 08:03:02 2020 -0500

Code for initial pass.

Forgot to create the repo and update it back in March, 2019. Will start with the original code. Will then take a look and answer a question posted in my blog.

Date:   Sun Jun 7 08:00:40 2020 -0500

```

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, refresh your knowledge and enhance your developer toolset!

One last thing, many thanks to all 1,122 subscribers to my blog!!!

Keep safe during the COVID-19 pandemic and help restart the world economy.

John

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.

## 5 thoughts on “Non-Divisible Subset”

1. Agustin says:

hello John, your explanation is very clear, thanks for that and hope your pizzas were delicious. I Regardless the excellent exposition of the problem and solution I can’t get to the bottom of this yet.
First of all, there is a primary issue related with the fact that I’m learning Go as my first language and it’s difficult to be sure if I understand everything I see in your code.
However, I’ll like to discuss the following test case:
15 7
278 576 496 727 410 124 338 149 209 702 282 718 771 575 436
11
With remainders [5 2 6 6 4 5 2 2 6 2 2 4 1 1 2] if I use // for (int i = 1; i <= (k / 2); i++) to group remainders i vs k-i (adapted to Go, of course) it always keep separated remainders 2 & 6.
This result in remainders == i [1,2] giving a sum of 8 elements and remainders == k-i [4,5,6] giving a sum of 7 elements.
In order to reach the max sum I think I need to match remainders [2,4,6] since their sum != k and have the maximum frequency of 11.
long story short: I cant group 2,4,6 following this logic. Clearly there must be something I am not getting right. I'd love if you could lend me a hint on this since I've suffered already enough with this problem 😀
I send you regards from Argentina and hope

1. JohnCanessa says:

Good day Agustin,

Hope all is well with you and in the area you live in Argentina.
It is a warm and sunny day in Apple Valley, Minnesota.
I understand Argentina is in winter but I believe different regions experience different microclimates.

First of all, I wish to apologize for not posting my Java solution on GitHub.
I edited the code to include and enable some comments.
Hope it is easier to get a copy and experiment with it.

The contents of remainderArr does not seem to match the numbers you mentioned.

As you can verify, the number of elements seems to return 11.

Hope this is of help and once again sorry for not putting the code on GitHub.

Regards;

John

PS: Good luck with Go.

1. Agustin says:

Hello John, thank you for updating your post. It’s very clear.
in regard of the weather it’s getting cold these days. I live in Cordoba, a city in the center of the country, near a beautiful area of low mountains and rivers. It’s really nice to spend the summers here. during winter it gets cold but normally not below zero Celsius degrees (freezing temperature), at least in the city. But right now it’s snowing up in the mountains so you can feel the cold wind down here.
In regard of the pandemic situation, it’s being taken care of so far. Thankfully the current president is being very responsible about the issue. However, the economic situation came from being devastating and just got worse with the pandemic. However, people in Argentina have masters in overcoming and accepting crisis, so psychologically speaking, it’s not so hard 😀
finally, at last but not least, the problem I was having I posted it in a different comment I wrote without noticing your response (my apologies). I was appending a new array with all the remainders from the original array (without organizing them)
Thank you for your response. I’m getting really thrilled by this new language I’m learning.
I’ve just started, with the pandemic, learning Go as my first approach to the programming world, self-taught with some friends. I am, however, close to people who work in programming and engineering of different fields but I am a Psychologist, so this is being new fuel for my neurons.
Today I finished another Hacker Rank’s problem, “Queens attack II”, it was hard and took a lot of lines but I was able know the way to proceed. Below the link.
I hope you are well in Apple Valley too. I don’t know the place yet, the U.S is very big but seems to share weather conditions with the state of New York, which I know and love its forest and state parks.
P.S, sorry for the long comment, but since you asked… 😉
https://www.hackerrank.com/challenges/queens-attack-2/submissions/code/163095842

1. JohnCanessa says:

Agustin,

Thanks for the message.
Glad all is going well for you and Argentina.
The pandemic has been a problem for everyone.
Hopefully light is at the end of the tunnel.
Several businesses are opening in the USA and around the world.

Seems that all is also going well with you, Go and JavaScript.
I like and enjoy learning, practicing and refreshing what I believe I know :o)

Good luck and keep safe;

John

2. Agustin says:

Hello, John, I wrote you earlier, I believe yesterday. I don’t know if you can read my previous comments.
However, my issue was here: ( remainderArr[n % k]++ ) I thought this was a way to append an array, so I was creating a new array of the same length of ‘s’ with the remainders. From there most of the outcomes were correct, but not for all. For example, in the test case |15 7|
278 576 496 727 410 124 338 149 209 702 282 718 771 575 436 I was not being able to group remainders 6 with remainders 2. So the solution was here: ( remainderArr[s[i]%k]++ ) and the rest was a peace of cake.