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 ! :slight_smile: 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