Common Divisors – HackerRank Solution

In this post, we will solve Common Divisors HackerRank Solution. This problem (Common Divisors) is a part of HackerRank Functional Programming series.

Task

First line of input contains an integer, T, which represent the number of test cases. Then follows T lines. Each line contains two space separated integers, M L, representing the points earned by Mario and Luigi, respectively.

Input

First line of input contains an integer, T, which represent the number of test cases. Then follows T lines. Each line contains two space separated integers, M L, representing the points earned by Mario and Luigi, respectively.

Output

For each test case, print the solution in different lines.

Constraints

• 1 <= T <= 10
• 1 <= L, M <= 10^8
• L, M are integers

Sample Input

3
10 4
1 100
288 240

Sample Output

2
1
10

Explanation

Test Case #00: Divisors of M = 10 are {1,2,5,10}, while for L = 4 they are {1, 2, 4}. So M and L shares {1, 2} as their common divisors.

Test Case #01: Here as M = 1, both players only share this number as their divisor.

Test Case #02: Here M and L shares 10 integers, {1,2,3,4,6,8,12,16,24,48}, as their divisors.

Solution – Common Divisors – HackerRank Solution

Scala

import java.util.Scanner

object Solution {
  def main(args: Array[String]): Unit = {
    val sc = new Scanner(System.in)

    val t = sc.nextInt
    (0 until t).foreach(_ => {
      val a = sc.nextInt
      val b = sc.nextInt

      def divisors(n: Int): Set[Int] = {
        def inner(v: Int): Set[Int] = if (v < 1) Set(n)
        else if (n % v == 0) inner(v - 1) + v + n / v
        else inner(v - 1)

        inner(math.sqrt(n).toInt)
      }

      println(divisors(a).intersect(divisors(b)).size)
    })
  }
}

Note: This problem (Common Divisors) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.