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

1. Create a hash table for equivalence classes (keys are 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.
2. We are only summing 2 elements at once thus only need to check pairs of our eq classes. And we know that for any i, the only elt j such that (i+j)%k = 0 is k-i. Thus we need only find which has the larger eq class: i or k-i. Find the max and sum them up.
3. be aware of k/2 (if k is even), and multiples of k. 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.

def nonDivisibleSubset(k, s):
    s_mod = [x % k for x in s]
    print(s_mod)
    s_count = 0
    for i in range(0, ((k // 2)+1)):
        c1 = s_mod.count(i)
        c2 = s_mod.count(k-i)
        if c1 > 0 or c2 > 0 :
            if i == 0:
                max_cnt_num = 1
            elif k/2 == i:
                max_cnt_num = 1
            else:
                max_cnt_num = max(c1,c2)
        else:
            max_cnt_num = 0
        print("MAX_CNT_NUM : ",max_cnt_num)
        s_count += max_cnt_num
        print("COUNT : ",s_count,'\n')
    print(s_count)
    return(int(s_count))

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 ...

    public static int nonDivisibleSubset(int k, List<Integer> s) {
        s=s.stream().map(item->item%k).collect(Collectors.toList());
        // Write your code here
        s=s.stream().sorted().collect(Collectors.toList());
        int max = 0;
        for (int i = 0; i < s.size(); i++) {
            List<Integer> ans = new ArrayList<>();
            ans.add(s.get(i));
            for (int j = i+1; j < s.size(); j++) {
                Integer needCheck = s.get(j);
                boolean match = true;
                for (Integer an : ans) {
                    if ((an + needCheck) % k == 0) {
                        match = false;
                        break;
                    }
                }
                if (match) {
                    ans.add(needCheck);
                }
            }
            if (max < ans.size()) {
                max = ans.size();
            }
        }
        return max;
    }