Huge GCD – HackerRank Solution

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

Task

Gayasen has received a homework assignment to compute the greatest common divisor of the two positive integers A and B. Since the numbers are quite large, the professor provided him with N smaller integers whose product is A, and M integers with product B. He would like to verify result, so he has asked you to write a program to solve his problem. But instead of printing complete answer you have to print answer modulo 10⁹+7.

Input

First line of input contains the positive integer N (1 <= N <= 1000).
Second line of input contains N space-separated positive integers not greater than 10⁴, whose product is the number A.
Third line of input contains the positive integer M (1 <= M <= 1000).
Fourth line of input contains M space-separated positive integers not greater than 10⁴, whose product is the number B.

Output

Print the greatest common divisor of numbers A and B modulo 1000000007.

Constraints

• 1 <= N, M <= 1000
• 1 <= element of list <= 10000

Sample Input #00

5
2 2 3 3 25
4
8 1 6 170

Sample Output #00

60

Sample Input #01

13
1 2 4 8 32 64 128 256 512 1024 2048 4096 8192
9
1 3 9 27 81 243 729 2187 6561

Sample Output #01

1

Sample Input #02

3
2 3 5
2
4 5

Sample Output #02

10

Explanation

Sample Case #00: Here A = 2×2×3×3×25 = 900, while B = 8×1×6×170 = 8160. Greatest common divisor of 900 and 8160 is 60.
Sample Case #01: In first list all number are of form 2^a and in second they are of form 3^a. As these two list doesn’t share any factor, their gcd is 1.
Sample Case #02: The greatest common divisor of numbers A(=30) and B(=20) equals 10.

Solution – Huge GCD – HackerRank Solution

Scala

import java.util.Scanner

object Solution {

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

    val n = sc.nextInt
    val as = (0 until n).map(_ => sc.nextInt)
    val m = sc.nextInt
    val bs = (0 until m).map(_ => sc.nextInt)

    sc.close()

    val maxValue = 10000
    val primeNumbers: IndexedSeq[Int] = (2 to maxValue).filter(v => BigInt(v).isProbablePrime(10))

    @scala.annotation.tailrec
    def toPrimes(value: Int, acc: Map[Int, Int] = Map(), index: Int = 0): Map[Int, Int] = if (index < primeNumbers.length) {
      val prime = primeNumbers(index)
      if (value % prime == 0) toPrimes(value / prime, {
        acc + (prime -> (acc.getOrElse(prime, 0) + 1))
      }, index)
      else toPrimes(value, acc, index + 1)
    }
    else acc

    def seqToPrimes(seq: Seq[Int]): Map[Int, Int] = seq.foldLeft(Map[Int, Int]())((acc, v) => toPrimes(v, acc))

    val a = seqToPrimes(as)
    val b = seqToPrimes(bs)

    val gcd = a.collect { case (key, value) if b.contains(key) => key -> math.min(value, b(key)) }

    val modulo = 1000000007
    println(gcd.foldLeft(1)((acc, pair) => {
      (BigInt(pair._1).modPow(pair._2, modulo) * acc % modulo).toInt
    }))
  }
}

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