Check if the pair sum of elements is divisible

Question

I am trying to find a more efficient solution to this question: https://practice.geeksforgeeks.org/problems/array-pair-sum-divisibility-problem/0

The problem statement is:

Given an array of integers and a number k, write a function that returns true if given array can be divided into pairs such that sum of every pair is divisible by k.

My solution(just the main logic):

for i in range(0,n):
        for j in range(i+1,n):
            if((a[i]+a[j])%k==0 and j not in res):
                res[i]=a[i]
                res[j]=a[j]
if(len(res)==n):
    print("True")
else:
    print("False")`

As evident, its a brute force solution that will work in O(n^2). I am basically adding the visited pairs to a list.

But is there a more efficient solution than this? Thanks for your time!

If you're satisfied with your solution working, and only want a better algorithm, check out this link. It describes a more efficient way to use hashing. geeksforgeeks.org/… — MPops

Dillon Davis Dillon Davis · Accepted Answer · 2018-06-29T21:35:04

For each number, you can check its remainder after division by K by taking the number N mod k. Then, for the sum of two numbers to be divisible by K, the sum of their remainders must be a multiple of k (including 0). So, if we keep track of each possible remainder, and make sure that each remainder is matched by its negation mod k, we can see if the pairing is possible.

def isPairable(array, k):
    modK = [0] * k
    for n in array:
        modK[ n % k] += 1
        modK[-n % k] -= 1

        if n % k == -n % k:
            modK[n % k] ^= 1

    return not any(modK)

Here modK holds sum counts of remainders modulo k, and for each number we increase the count of n % k remainders, and decrease the negation -n % k, to account for the element we'd pair with. If n % k == -n % k, then we must toggle between zero and nonzero at each occurrence.

Check if the pair sum of elements is divisible

1 Answers