Check if the pair sum of elements is divisible

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
Jun 29 at 21:30

hashing

1 Answer
1

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.

modK

n % k

-n % k

n % k == -n % k

Right idea. Algo has a couple of failure modes though.
– spinkus
Jun 29 at 23:38

Care to provide some counterexamples? I'd be more than happy to correct it if I know what's wrong.
– Dillon Davis
Jun 29 at 23:41

Ah, when k == n/2, it adds and subtracts from the same element. Array = [3], k = 6. I'll fix it- thanks for the heads up.
– Dillon Davis
Jun 29 at 23:46

Still has at least one failure mode: k=8, data=[8,12]
– spinkus
Jun 30 at 0:42

Thanks @spinkus, fixed. I quit trying to be clever / efficient, and explicitly wrote out the edge case.
– Dillon Davis
Jun 30 at 0:56

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.