Divisible Sum Pairs Algorithm

In this article, I'll be describing how I solved the Divisible Sum Pairs Challenge on HackerRank using Python 3.

This challenge is part of the Implementation challenges in the Algorithm section on HackerRank.

Problem 🎲

Given an array of integers and a positive integer k, determine the number of (i, j) pairs where i < j and ar[i] + ar[j] + is divisible by k.

Example

Samle Input 0:

ar = [1, 2, 3, 4, 5, 6]
k = 5

Three pairs meet the criteria: [1, 4], [2, 3], and [4, 6].

Samle Ouput 0:

3

Samle Input 1:

Samle Ouput 1:

Explanation 1

Here are the 5 valid pairs when k = 3:

I'll get right into the algorithm. Please feel free to read the full question on HackerRank.

Solution 🔎

Let's consider Sample Input 1

In plain English, we have an array of integers, and we need to count how many times the sum of any given pair is divisible by an integer k. However, the first item in this pair must be less than the second.

Hence: Given an array ar, count the number of (i, j) pairs where i < j and ar[i] + ar[j] + is divisible by k.

Pretty straightforward problem this time. Let's code this out! 👨🏽‍💻

Step 1️⃣: Sort array, ar:

1. We know that the first item in this pair must be less than the second, i < j,
2. So we'll start by sorting ar.

ar.sort()

>> [1, 1, 2, 2, 3, 6]

Step 2️⃣: Loop through the sorted array and evaluate the condition:

• The condition to be evaluated on each iteration is to check if the sum of any given pair is divisible by the integer k.

1. We'll initialise a counter variable to track how many times this condition occurs.
2. Two for loops will be used to solve this problem:
   • The first for loop will loop forwards through the sorted array from the integer being considered up until the second to the last one.

     for i in range(0, n-1):
     

   • The second for loop will loop backwards, from the last integer in the sorted array to the integer after the one being considered.

     for j in range((n-1), i, -1):
     

I'll explain further while developing our conditional logic.

Step 3️⃣: Developing the conditional logic within the two for loops:

While iterating through the sorted array, we need to check if the sum of any given pair is divisible by the integer k.

Here's how we'll do it.

1. For a given integer ar[i] in the sorted array, we'll check if the sum of that integer and the next integer from the decreasing loop ar[j] is divisible by k.
2. Since we are only concerned with the counts and not the actual pair, we can evaluate this condition easily.
3. Once this condition returns true, we'll update the counter by 1.

Let's look at this conditional logic graphically:

Step 4️⃣: Putting it all together:

Full code:

def divisibleSumPairs(n, k, ar):
    # Write your code here
    counter = 0
    ar.sort()

    for i in range(0, n-1):
        for j in range((n-1), i, -1):
            if (ar[i] + ar[j]) % k == 0:
                counter += 1

    print(counter)


divisibleSumPairs(6, 3, [1, 3, 2, 6, 1, 2])
>> 5

Bonus Tip:

A more pythonic way is to use a list comprehension:

def divisibleSumPairs(n, k, ar):
    # Write your code here
    counter = 0
    ar.sort()

    result = [counter+1 for i in range(0, n-1) for j in range((n-1), i, -1) if (ar[i] + ar[j]) % k == 0 ]
    print( sum(result) )

divisibleSumPairs(6, 3, [1, 3, 2, 6, 1, 2])
>> 5

• You can guess that the second method is more performant, but either one should pass all test cases.🤓

Hope this helps with understanding this challenge. Happy Coding!👨🏽‍💻