Computing the GCD – HackerRank Solution

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

Objective

In this challenge, we learn how to compute GCD using the Euclidean algorithm.

Resource

Given two integers, x and y, a recursive technique to find their GCD is the Euclidean Algorithm.

The algorithm states that, for computing the GCD of two positive integers x and y, if x and y are equal, GCD(x, y) = x. Otherwise GCD(x, y) = GCD(x – y, y) if x > y. There are a few optimizations that can be made to the above logic to arrive at a more efficient implementation.

Task

Given the starter code, you need to complete a function body that returns the GCD of two given integers x and y.
The task of reading in input and printing the output will be handled by us.

Programming Language Support
At this point of time, we have a template for Scala. This means that we provide the code required to accept the input and display the output.

Input Format

One line of input containing 2 space separated integers.

Constraints

• 1 <= a, b <= 10⁶

Output Format

Output one integer, the GCD of the two given numbers.

Sample Input

1 5 

Sample Output

1

Explanation

GCD(1,5) = 1  
GCD(10,100) = 10  
GCD(22,131) = 1

Solution – Computing the GCD – HackerRank Solution

Scala

object Solution {
  def main(args: Array[String]): Unit = {
    /** The part relates to the input/output. Do not change or modify it **/
    acceptInputAndComputeGCD(readLine().trim().split(" ").map(x => x.toInt).toList)
  }

  /** This part handles the input/output. Do not change or modify it **/
  def acceptInputAndComputeGCD(pair: List[Int]): Unit = {
    println(gcd(pair.head, pair.reverse.head))
  }

  def gcd(x: Int, y: Int): Int = {
    @scala.annotation.tailrec
    def innerGcd(a: Int, b: Int): Int = if (b == 0) a else innerGcd(b, a % b)

    val (a, b) = if (x > y) (x, y) else (y, x)
    innerGcd(a, b)
  }

  // readLine() is deprecated in Scala 13, but it is called by HackerRank's predefined code.
  // So it is added to fix the issue.
  def readLine(): String = scala.io.StdIn.readLine()
}

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