I'm trying to solve the HackerRank excercise "Non-Divisible Subset" https://www.hackerrank.com/challenges/non-divisible-subset/

Excercise track The exercise track is about creating a program that will take in a list of integers and a number 'k', and will output the count of the maximum number of integers in the list that are not divisible by 'k' and are non-repeating.

My problem is that results differs from Expected output. Can you detect any problems in my code? Probably it's a logic error but I'm stuck. Please help me.

With input k=9 and input list = 422346306, 940894801, 696810740, 862741861, 85835055, 313720373, output should be 5 but my code get 6.

public static int nonDivisibleSubset(int k, List<int> s)
    {
        var x = GetPerm(s);


        var y = x.Where(x => x.Value % k != 0).Select(x=>x.Key).ToList();
        var a = y.SelectMany(x => x).ToHashSet();

        return a.Count();

    }

    static Dictionary<List<int>,int> GetPerm (List<int> list)
    {
        Dictionary<List<int>,int> perm = new Dictionary<List<int>, int>();

        for (int i = 0; i < list.Count; i  )
        {
            for (int j = i 1; j < list.Count; j  )
            {
                List<int> sumCouple = new List<int>();
                sumCouple.Add(list[i]);
                sumCouple.Add(list[j]);
                perm.Add(sumCouple, sumCouple.Sum());
            }

        }
        return perm;
    }

CodePudding user response：

As I can see the actual problem is quite different:

Given a set of distinct integers, print the size of a maximal subset of where the sum of any numbers in is not evenly divisible by k.

If we have a look at the example:

list = {422346306, 940894801, 696810740, 862741861, 85835055, 313720373} 
k = 9

we can't take all 6 numbers since 940894801 313720373 is evenly divisible by k = 9. The required subset is all but last item: {422346306, 940894801, 696810740, 862741861, 85835055}

And the solution will be different as well:

public static int nonDivisibleSubset(int k, List<int> s)
{
    Dictionary<int, int> remainders = s
        .GroupBy(item => item % k)
        .ToDictionary(group => group.Key, group => group.Count());
        
    int result = 0;
    
    foreach (var pair in remainders) {
        if (pair.Key == 0 || pair.Key % (k / 2) == 0 && k % 2 == 0)
            result  = 1;
        else if (!remainders.TryGetValue(k - pair.Key, out int count))
            result  = pair.Value;
        else if (count < pair.Value)
            result  = pair.Value;
        else if (count == pair.Value && pair.Key < k - pair.Key)
            result  = pair.Value;
    }   
    
    return result;  
}

The idea is to group by all the numbers by their remainder when devided by k. Then we do the follow:

• if remainder is 0 or k / 2 (for even k) we can take just one such number into the subset
• if remainder is x we can add to subset either all such numbers or all the numbers which has remainder k - x.

Time complexity: O(n) Space complexity: O(n)

CodePudding user response：

Not an answer to the question - but there is at least one problem with your code - List's can't be used as a key for dictionary as is cause it does not override Equals/GetHashCode, so it will perform reference comparison. You can provide a custom equality comparer:

class PairListEqComparer : IEqualityComparer<List<int>>
{
    public static PairListEqComparer Instance { get; } = new PairListEqComparer();

    public bool Equals(List<int> x, List<int> y)
    {
        if (ReferenceEquals(x, y)) return true;
        if (ReferenceEquals(x, null)) return false;
        if (ReferenceEquals(y, null)) return false;
        if (x.Count != 2 || y.Count != 2) return false; // or throw

        return x[0] == y[0] && x[1] == y[1];
    }

    public int GetHashCode(List<int> obj) => HashCode.Combine(obj.Max(), obj.Min(), obj.Count);
}

And usage:

Dictionary<List<int>,int> perm = new Dictionary<List<int>, int>(PairListEqComparer.Instance);

Or consider using ordered value tuples (compiler will generate the needed methods). From that you can think about optimizations and better algorithm.

As for solution itself - valid brute-force approach would be to generate all permutations of all sizes, i.e. from 1 to s.Count and find the longest one which satisfies the condition (though I doubt that it will be efficient enough for hackerrank)