We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Non-Divisible Subset
Non-Divisible Subset
Sort by
recency
|
808 Discussions
|
Please Login in order to post a comment
This is a tough problem, not least because the description tacitly leads you to an exhaustive search. As you begin implementing this solution it should be clear this will take forever if the size of the set is not small. One way to reduce the size of the set it to consider the equivalence classes modulo k, instead of the elements themselves. However, this set can still have as many as k elements. The solution needs to be constructive - i.e. you must construct the largest subset. There are undoubtably faster ones, but a readable solution looks like
i%k
; values are arrays containing all elts with that modulo), then from this create a hash table with the same keys, but values are the lengths of the value arrays above.i
, the only eltj
such that(i+j)%k = 0
isk-i
. Thus we need only find which has the larger eq class:i
ork-i
. Find the max and sum them up.k/2
(ifk
is even), and multiples ofk
. Each can have only 1 element in the set. This can be addressed in the hash table containing the lengths of the eq-classes.Putting the required function with different logic: 1. Create a list of reminders for k for each from the given list s. 2. Logic is to identify the sum of reminder's pair to be k 3. Eliminate the reminder with lower count in the created reminder list for each reminder pair. 4. add for the edge condition at i==0 (when only one value can be added such that when added to any other no. the reminder for the sum is not 0 when done with k 5. Add for edge condition when k/2 == i (with the same logic as above) 6. Add the count for each pair of reminders, where the count is the max of the frequency of reminders between the two pairs.
Here is problem solution in Python, Java, C++, C and Javascript - https://programmingoneonone.com/hackerrank-non-divisible-subset-problem-solution.html
I think test case 6 is incorrect. Given: n=5 k=1 s = [1 2 3 4 5] The "correct" output is 1 but all whole numbers are divisible by 1. Shouldn't the actual answer be 0 since a subset of size zero has no elements divisible by k?
I implemented algorithm in Java , and after testing , I found that in Test Case 5 , the expected result is 50 , but my actual calculation is 45 , Has anyone encountered this issue?
I know the issue is on my side , Please , could someone help me check where the problem is in my Code ,
The following is my code ...