!!! UPDATE !!!
This post has been updated in order to add comments to the code and add the source code to GitHub. Apparently I forgot to create a repository. Sorry about that.
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) 2019 Microsoft Corporation. All rights reserved.
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
06/03/2020 04:20 PM <DIR> Downloads
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> Links
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 622 README.md
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
C:\Users\johnc\workspace0\NonDivisibleSubset>type README.md
# 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.
I apologize for not uploading the code back in March, 2019.
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 add Solution.java
# **** ****
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
# **** ****
C:\Users\johnc\workspace0\NonDivisibleSubset>git commit -m "added comments"
[master 43a5c72] added comments
1 file changed, 50 insertions(+), 31 deletions(-)
# **** ****
C:\Users\johnc\workspace0\NonDivisibleSubset>git status
On branch master
Your branch is ahead of 'origin/master' by 1 commit.
(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
7bc0ad9..43a5c72 master -> master
# **** ****
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
commit 43a5c72bcab5384bc0e1e92636d883ea2add3616 (HEAD -> master, origin/master, origin/HEAD)
Author: JohnCanessa <john.canessa@gmail.com>
Date: Sun Jun 7 10:39:13 2020 -0500
added comments
commit 7bc0ad916bbc3a365f2d127dfe1076499865502f
Author: John Canessa <8019504+JohnCanessa@users.noreply.github.com>
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.
commit 270189d3d8ebddbf6f0abe71bea5e62adcc40a66
Author: John Canessa <8019504+JohnCanessa@users.noreply.github.com>
Date: Sun Jun 7 08:00:40 2020 -0500
Create README.md
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
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.
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
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.
In the updated post I have make some manual additions besides enabling and adding comments.
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.
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
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
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.
Thank you for updating your post with specific info about this point.