Order exercises – HackerRank Solution

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

Task

During a math class, a teacher wanted to practice ordering with students. He gave an array of N integers, a = {a₁, a₂, . . . ,a_N} to the students along with following definitions:

• Subarray is a contiguous segment of array. For example a[l, r] = {a_l, a_l+1, . . . , a_r} is a subarray, where 
• We say that a sum of a subarray X(=a[xl, xr] = {a_xl, a_xl+1, . . . , a_xr}) is a sum of elements in this subarray
• We say that subarray  is greater than subarray  if and only if:
  • X has a greater sum than Y
  • X and Y has the same sum and X begins earlier
  • X and Y has the same sum, they start in the same place and the length of X is smaller than the length of Y

Since the teacher doesn’t like number 0, there is no 0 in the array a. Other than array a, the teacher also gave an integer K. The task is to lists as many as possible, but not more than K, subarrays with a positive sum in the following order.

• The first subarray is the greatest subarray in the array according to above definition.
• The i^th subarray is the greatest subarray disjoint to any of the j^th subarray, where j < i (disjoint means that they have no common elements).

Of course in order to win with others, you have to solve the problem first.

Input

In the first line there are two integers N and K separated by a single space.
In the second line there are N integers separated by single space denoting the array arr.

Output

Print no more than K lines. In the i^th line print the sum of the i^th sequence in the above order.

Constraints

• 1 <= N <= 10⁵
• 1 <= K <= N
• 0 < |a_i| <= 104, where i ∈ [1, N]

Sample Input 00

5 3
2 4 -10 2 -2

Sample Output 00

6
2

Explanation

Subarray a[1, 2] = {a1, a2} has sum 6 and this is the greatest value in the whole array. Next disjoint greatest subarray is a[4, 4] = a₄ with sum = 2. There are no more subsequences with a positive value disjoint with the first and the second subsequence.

Sample Input 01

4 2
-2 5 -1 -8

Sample Output 01

5  

Explanation 01

Subarray a[2, 2] = {a2} has sum 5 and this is the greatest value in the whole array. There are no more subsequences with a positive value disjoint with the first one, so even if K = 2, we print out just one value.

Solution – Order exercises – HackerRank Solution

Scala

import java.util.Scanner

import scala.collection.immutable.Queue

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

    sc.nextInt
    val k = sc.nextInt
    sc.nextLine
    val a = sc.nextLine.split(" ").map(_.toInt)

    sc.close()

    case class Acc(list: List[Int])
    val sentinel = Int.MaxValue / 2
    val temp = a.foldLeft(Acc(List(-sentinel, sentinel)))((acc, v) => acc.list match {
      case Nil if v < 0 => acc
      case Nil => Acc(v :: Nil)
      case list@x :: xs => if ((v < 0) == (x < 0)) Acc(x + v :: xs) else Acc(v :: list)
    }).list

    val compressed = if (temp.head < 0) temp.tail else temp

    println(solve(compressed)
      .sortBy(-_)
      .take(k)
      .mkString("\n")
    )
  }

  def solve(seq: List[Int]): List[Int] = {
    case class Accumulator(totalSum: Int, queue: Queue[Int], answer: List[Int])

    @scala.annotation.tailrec
    def inner(seq: List[Int], acc: Accumulator): List[Int] = {
      seq match {
        case Nil =>
          acc.answer
        case xPos :: xs if acc.queue.isEmpty =>
          //empty queue
          inner(xs, Accumulator(xPos, Queue(xPos), acc.answer))
        case xNeg :: xPos :: xs =>
          val (nextSeq, nextAcc) = {
            val sNeg = acc.totalSum + xNeg
            if (sNeg <= 0) {
              val (firstPos, tempQueue) = acc.queue.dequeue

              if (tempQueue.isEmpty) {
                //All items in queue are processed.
                (xs, Accumulator(xPos, Queue(xPos), firstPos :: acc.answer))
              } else {
                if (acc.totalSum >= firstPos) {
                  //Glue items in queue.
                  (xs, Accumulator(xPos, Queue(xPos), acc.totalSum :: acc.answer))
                } else {
                  //Separate first item in queue.
                  val (_, nextQueue) = tempQueue.dequeue
                  (nextQueue.toList ++ seq, Accumulator(0, Queue(), firstPos :: acc.answer))
                }
              }
            } else {
              val sPos = sNeg + xPos
              if (sPos >= acc.queue.head) {
                //Glue
                (xs, Accumulator(sPos, Queue(sPos), acc.answer))
              } else {
                //Uncertain
                (xs, Accumulator(sPos, acc.queue.enqueue(xNeg).enqueue(xPos), acc.answer))
              }
            }
          }

          inner(nextSeq, nextAcc)
      }
    }

    inner(seq, Accumulator(0, Queue(), Nil))
  }
}

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