# Making solution to Hackerrank Problem functional

Hello! I’m trying to solve Hackerrank Problems in a functional way. So far I haven’t been successful with this one: https://www.hackerrank.com/challenges/divisible-sum-pairs/problem .

My (imperative solution is):

``````   def divisibleSumPairs(n: Int, k: Int, ar: Array[Int]): Int =  {
var count = 0
for(i <- 0 to n - 1){
for (j <- i + 1 to n -1){
if ((ar(i) + ar(j))%k==0)
count+=1
}
}
count
}
``````

Suggestions? Also I would like to avoid the nested loop as is not really efficient.

First, there is the straight-forward translation of what you have to something more functional: get all pairs, filter by divisibility (untested).

(no need for n, that’s just ar.length)

def divisibleSumPairs(k: Int, ar: Array[Int]): Int = {

** val indices = 0 until ar.length**

** indices.flatMap(i => indices.map(j => (i, j))).filter{ case (i, j) =>
i < j && (ar(i) + ar(j)) % k == 0
}.size**

}

That’s functional, but not very efficient. More efficient would be to count how often each value for (ar(i) % k) appears and calculate the result (untested):

def divisibleSumPairs(k: Int, ar: Array[Int]): Int = {

** val moduloCounts = ar.groupBy(_ % k).mapValues(_.size).view.force**

** val keys = moduloCounts.keySet**

** keys.flatMap(key1 => keys.map(key2 => (key1, key2))).map { case (key1, key2) =>**

** if(key1 == key2) {**

** val moduloCount = moduloCounts(key1)**

__ moduloCount*(moduloCount - 1)__

** } else {**
__ moduloCounts(key1)*moduloCounts(key2)__

** }**

** }.sum**

}

I haven’t tested the code above, so there may be bugs, but this shows how it can be done.

Best, Oliver

Ah, found one bug - in the key1 == key2 case, we need to divide by two to compensate for double-counting:

def divisibleSumPairs(k: Int, ar: Array[Int]): Int = {

** val moduloCounts = ar.groupBy(_ % k).mapValues(_.size).view.force**

** val keys = moduloCounts.keySet**

** keys.flatMap(key1 => keys.map(key2 => (key1, key2))).map { case (key1, key2) =>**

** if(key1 == key2) {**

** val moduloCount = moduloCounts(key1)**

__ moduloCount*(moduloCount - 1)/2__

** } else {**
__ moduloCounts(key1)*moduloCounts(key2)__

** }**

** }.sum**

}

Best, Oliver

Thanks very much ! I also found this solution

`````` def divisibleSumPairs(k: Int, ar: Array[Int]): Int =  {
def formula(x: List[(Int, Int)]) = {
if ((x(0)._2 < x(1)._2) && ((x(0)._1 + x(1)._1) % k == 0)) 1 else 0
}

ar
.zipWithIndex
.toList
.combinations(2)
.map(formula).sum
}
``````

But I don’t know how methods like `zipWithIndex` and `combinations(_)` affect the efficiency of the algorithm.

Hello,

This solution, similarly to my first one, creates all possible pairs, which are many (n^2) if the list is long. So, for long lists, the second solution is clearly better. If performance is a concern, we could replace the groupBy-map-view-force part by something that just counts instead of creating sub-collections.

Best, Oliver