Expressions – HackerRank Solution

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

Task

5 year old Shinchan had just started learning Mathematics. Meanwhile, one of his studious classmate, Kazama, had already written a basic calculator which supports only 3 operations on integral numbers: multiplication (*), addition (+), and subtraction (-). Since he had just learnt about these operations, he didn’t have knowledge of precedence of operators, and in his calculator all operators had same precedence and left associativity.

As always Shinchan started to irritate him with his silly question. He gave Kazama a list of N integers and asked him to insert one of the above operators between each pair of consecutive integer such that the result obtained after feeding the resulting expression in Kazama’s calculator is divisible by 101. At core Shinchan is a good guy, so he gave only that list of integers for which the answer always exists.

Can you help Kazama in creating the required expression? If multiple solutions exists, print any one of them.

Input Format

First line contains an integer, N, representing the number of elements in the list. In next line there are N space separated integers representing the list.

Constraints

• 2 <= N <= 10⁴
• 1 <= element of list <= 100
• Length of output expression should not exceed 10 x N.

Note

• You are not allowed to permute the list.
• All operators have same precedence order and left associativity, ie., a + b * c – d * e = ((((a + b) * c) – d) * e)
• Unary plus and minus are not supported, ie., statement like –a, a * –b, -a * b + c are invalid.

Output Format

Print the resultant expression. You can insert 0 or more spaces between operators and operands.

Sample Input 0

3
22 79 21

Sample Output 0

22*79-21

Explanation 0

Solution 1: 22 * 79 – 21 = 1717, where 1717 / 101 = 17 and it is perfectly divisible by 101.
Solution 2: 22 + 79 * 21 = (22 + 79) * 21 = 2121, which is another multiple of 101.

Sample Input 1

5
55 3 45 33 25

Sample Output 1

55+3-45*33-25

Explanation 1

55 + 3 – 45 * 33 – 25 = ((((55 + 3) – 45) * 33) – 25) = 404 which is also divisible by 101.

Solution – Expressions – HackerRank Solution

Scala

import java.util.Scanner

import scala.collection.mutable

object Solution {

  private val data = mutable.Map[(Long, List[Int]), Acc]()

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

    val n = sc.nextInt
    val numbers = (0 until n).map(_ => sc.nextInt).toList

    println(solve(numbers))

    sc.close()
  }

  def solve(numbers: List[Int]): String = {
    val operations = List('+', '-', '*')

    val modulo = 101

    def inner(numbers: List[Int], acc: Acc): Acc = data.getOrElseUpdate((acc.result % modulo, numbers),
      numbers match {
        case Nil =>
          if (acc.result % modulo == 0)
            Acc(acc.result, acc.operations, found = true)
          else acc
        case v :: vs =>
          operations.foldLeft(Acc(0, Nil))((innerAcc, op) => if (innerAcc.found) innerAcc else {
            val nextResult = op match {
              case '+' => acc.result + v
              case '-' => acc.result - v
              case '*' => acc.result * v
            }
            inner(vs, Acc(nextResult, op :: acc.operations))
          })
      }
    )

    val answer = inner(numbers.tail, Acc(numbers.head, Nil)).operations.reverse
    numbers.tail.zip(answer).foldLeft(new StringBuilder(numbers.head.toString))((acc, v) => acc ++= s"${v._2}${v._1}").toString
  }

  case class Acc(result: Long, operations: List[Char], found: Boolean = false)

}

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