# 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.

Contents

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 109+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 104, 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 104, 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) {
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.