Algorithm Divisible Sum Pairs

Question

I did the Divisible Sum Pairs problem on HackerRank

input: n is length of array ar, k is an integer value.
a pair is define only if ar[i]+ar[j] is dividable by k where i < j.
Problem: find and return pairs in array.

def divisibleSumPairs(n, k, ar):
    i=0       #pointer 1
    j=1       #pointer 2 is faster than p1  
    count =0  #pointer 3 will only increment 1 once j = n-1 (second last element)
    pairs=0
    while count < n-1:
        if (ar[i]+ar[j])%k==0: 
            pairs+=1
        j+=1
        count+=1
        if count==n-1:
            i+=1
            j=i+1
            count =i
    print(pairs)

Code visualized

step 1:
 i  j
[a][b][c][e][f]
compare (i,j)
 i     j
[a][b][c][e][f]
compare (i,j)
 i        j
[a][b][c][e][f]
compare (i,j)
 i           j
[a][b][c][e][f]
compare (i,j)
i+=1
j=i+1

step2
    i  j
[a][b][c][e][f]
compare (i,j)
        .
        .
        .
        .
step n
          i  j
[a][b][c][e][f]
compare (i,j)
finish

I have a couple of questions:

1. Does this algorithm have a name?
2. Is there other way (maybe better, faster)?
3. Is there some code I could have done better/ differently?

#some test data n=6 , k=3 ar =[1, 3, 2, 6, 1, 2]

Answer 1

Your code is not Pythonic as it does not adhere to the standard Python style guide.

1. divisibleSumPairs should be snake case divisible_sum_pairs.
2. You should have one space both sides of most operators. i=0 i+=1, ar[i]+ar[j] are all harder to read than they need to be.
3. Most of your variable names don't describe what they contain.
4. You print inside a function that should return.

def divisible_sum_pairs(length, divisor, items):
    i = 0       #pointer 1
    j = 1       #pointer 2 is faster than p1
    count = 0   #pointer 3 will only increment 1 once j = n-1 (second last element)
    pairs = 0
    while count < length - 1:
        if (items[i] + items[j]) % divisor == 0: 
            pairs += 1
        j += 1
        count += 1
        if count == length - 1:
            i += 1
            j = i + 1
            count = i
    return pairs

5. You don't need pointer 3 as count = j + 1:

   j += 1
   count += 1
   

   j = i + 1
   count = i
   

   We can just replace count with j - 1.

6. We can simplify all of the places where count was being used. This is as you have - 1s on both sides of the operators.

7. Rather than while j < length it would be clearer if you instead used while i < length - 1. This comes in two parts:

   • It is confusing to see while j < length with if j == length in the body.
   • You're not actually bound by j you're bound by i.

8. Rather than using a while loop we can see that there's an opportunity to use two for loops to make things easier to read.

   Note: These for loops have the exact same time complexity as your while.

def divisible_sum_pairs(length, divisor, items):
    pairs = 0
    for i in range(length - 1):
        for j in range(i + 1, length):
            if (items[i] + items[j]) % divisor == 0: 
                pairs += 1
    return pairs

9. We can simplify the code by using using a comprehension.

   For example we can extract getting the combinations of items.

   combinations = (
       (items[i], items[j])
       for i in range(length - 1)
       for j in range(i + 1, length)
   )
   for a, b in combinations:
       if (a + b) % divisor == 0:
   

10. We can instead sum with a comprehension that generates numbers.

    pairs = sum(
        1
        for a, b in combinations
        if (a + b) % divisor == 0
    )
    

11. We can exploit the fact that bools are integers and move the if's expression as the comprehension's expression.

12. We can use itertools.combinations to remove the need to manually get the combinations.

import itertools


def divisible_sum_pairs(_, divisor, items):
    return sum(
        (a + b) % divisor == 0
        for a, b in itertools.combinations(items, 2)
    )

Every change has been a 1 to 1 replacement. The time complexity is still \$O(\binom{n}{2})\$ (\$O(n^2)\$) and memory complexity is still \$O(1)\$.

However now readability is much better.