Lists and GCD – HackerRank Solution

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

Task

You are given the elements of list, list, in the representation provided above. Find its greatest common divisor, i.e., gcd(list).

Input Format

First line contains an integer, q, which is the size of list, lst.
Then follows q lines, where i^th line represents the factors of i^th element of lst, l_i

Output Format

Print one line representing the greatest common divisor of lst (gcd(lst)) in the above representation.

Constraints

• 2 <= q <= 1000
• All other integers lie in [1, 10⁵]
• 1 <= Total number of prime factors of an element <= 100

Notes

• Test cases are designed such that gcd(lst) will always be greater than 1.

Sample Input #00

2
7 2
2 2 7 1

Sample Output #00

7 1

Sample Input #01

4
2 2 3 2 5 3
3 2 5 3 11 1
2 2 3 3 5 4 7 6 19 18
3 10 5 15

Sample Output #01

3 2 5 3

Explanation

Test case #00: lst = {7², 2² x 7¹}. Therefore gcd(lst) = 7¹.
Test case #01: lst = {2² x 3² x 5³, 32 x 5³ x 11¹, 2² x 3³ x 5⁴ x 7⁶ x 19¹⁸, 3¹⁰ x 5¹⁵} * gcd(lst) = 32 x 5³. 

Solution – Lists and GCD – HackerRank Solution

Scala

import java.util.Scanner

object Solution {

  def main(args: Array[String]): Unit = {
    case class Item(p: Int, n: Int) {
      override def toString: String = s"$p $n"
    }

    val sc = new Scanner(System.in)

    val Q = sc.nextInt
    sc.nextLine
    val items = (0 until Q).flatMap(_ => sc.nextLine.split(' ').map(_.toInt).grouped(2).map(arr => Item(arr.head, arr.last)))
      .groupBy(_.p)
      .map { case (p, list) => (p, list.length, list.map(_.n).min) }
      .collect { case (p, Q, n) => Item(p, n) }
      .toSeq
      .sortBy(_.p)

    println(items.mkString(" "))
    sc.close()
  }
}

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