Subset with no pair sum divisible by K

Subset with no pair sum divisible by K

Given an array of integer numbers, we need to find maximum size of a subset such that sum of each pair of this subset is not divisible by K.

Input :  arr[] = [3, 7, 2, 9, 1]  
         K = 3
Output : 3
Maximum size subset whose each pair sum 
is not divisible by K is [3, 7, 1] because,
3+7 = 10, 
3+1 = 4, 
7+1 = 8  all are not divisible by 3.
It is not possible to get a subset of size 
bigger than 3 with the above-mentioned property.

We can solve this problem by computing modulo of array numbers with K. if sum of two numbers is divisible by K, then if one of them gives remainder i, other will give remainder (K – i). First we store frequencies of numbers giving specific remainder in a frequency array of size K. Then we loop for all remainders i and include max(f[i], f[K – i]). Why? a subset with no pair sum divisible by K must include either elements with remainder f[i] or with remainder f[K – i]. Since we want to maximize the size of subset, we pick maximum of two sizes.
In below code array numbers with remainder 0 and remainder K/2 are handled separately. If we include more than 2 numbers with remainder 0 then their sum will be divisible by K, so we have taken at max 1 number in our consideration, same is the case with array numbers giving remainder K/2.

Time Complexity : O(N + K)
Auxiliary Space : O(K)

    // Returns maximum size of subset with no pair

    // sum divisible by K

    static int subsetPairNotDivisibleByK(int arr[], 

                                      int N, int K)

    {

          

        // Array for storing frequency of modulo

        // values

        int f[] = new int[K];

        Arrays.fill(f, 0);

      

        // Fill frequency array with values modulo K

        for (int i = 0; i < N; i++)

            f[arr[i] % K]++;

      

        // if K is even, then update f[K/2]

        if (K % 2 == 0)

            f[K/2] = Math.min(f[K/2], 1);

      

        // Initialize result by minimum of 1 or

        // count of numbers giving remainder 0

        int res = Math.min(f[0], 1);

      

        // Choose maximum of count of numbers

        // giving remainder i or K-i

        for (int i = 1; i <= K/2; i++)

            res += Math.max(f[i], f[K-i]);

      

        return res;

    }