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]

• impopularGuy: Welcome to CodeReview. Did you check the discussions on HackerRank for this challenge? There is a decent solution posted there with explanation. You can find it here
• MisterIvan: Thanks @impopularGuy. I did. However, the top voted code, written by usinha02, is stated to be O(n) time complexity. I don't understand how this can be when the code is using nested for loops? Shouldn't it then be O(n^2) time complexity? I guess it has something to do with the way the array is split into buckets of k i%k where i= 0,1,..k divide and conquer -ish?
• impopularGuy: I agree that the one I linked is not O(n) but is rather O(nk). However have a look at an explanation and the python implementation

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.

• Maarten Fabré: nice answer. Only remark I have is that instead of the for i in range(length - 1) in the intermediate solution, I would introduce enumerate here.
• Peilonrayz: @MaartenFabré I had thought of using enumerate but getting all bar the last value with it is not really that clean.