Find subarray with given sum

Question

I am trying to implement functional style of finding subarray with given sum. Code i wrote is not up to functional style. Can someone help to make it more functional.

Problem : Given an unsorted array of nonnegative integers, find a continous subarray which adds to a given number.

Input: arr[] = {1, 4, 20, 3, 10, 5}, sum = 33 Ouptut: Sum found between indexes 2 and 4

Input: arr[] = {1, 4, 0, 0, 3, 10, 5}, sum = 7 Ouptut: Sum found between indexes 1 and 4

I could solve this problem in brute force approach. But looking for more effective functional solution.

val sumList = list.foldLeft(List(0), 0)((l, r) => (l._1 :+ (l._2+r), l._2 + r))._1.drop(1)
  //Brute force approach
  sumList.zipWithIndex.combinations(2).toList.collectFirst({
    case i if i(1)._1 - i(0)._1 == sum => i
  }) match {
    case Some(List(x, y)) => println("elements which form the given sum are => "+ list.drop(x._2+1).take(y._2-x._2))
    case _ => println("couldn't find elements which satisfy the given condition")
  }

Algorithm : Initialize a variable curr_sum as first element. curr_sum indicates the sum of current subarray. Start from the second element and add all elements one by one to the curr_sum. If curr_sum becomes equal to sum, then print the solution. If curr_sum exceeds the sum, then remove trailing elemnents while curr_sum is greater than sum.

 val list:List[Int] = List(1, 4, 20, 3, 10, 5)
  val sum = 33
    
  val (totalSum, start, end, isSumFound) = list.zipWithIndex.drop(1).foldLeft(list.head, 0, 1, false)((l, r) =>
    if(!l._4) {
      val tempSum = l._1 + r._1
      if (tempSum == sum){
        (sum, l._2, r._2, true)
      } else if(tempSum > sum){
          var (curSum, curIndex) = (tempSum, l._2)
          while(curSum > sum && curIndex < list.length-1){
            curSum = curSum - list(curIndex)
            curIndex = l._2 +1
          }
        (curSum, curIndex, r._2, curSum == sum)
      } else {
        (tempSum, l._2, r._2, false)
      }
    }else
      l
  )

  if(isSumFound || totalSum == sum){
    println("elements which form the given sum are => "+ list.drop(start+1).take(end-start))
  }else{
    println("couldn't find elements which satisfy the given condition")
  }

Your sumList is more neatly expressed as val sumList = list.scanLeft(0){_ + _} — The Archetypal Paul
Hmm. and append .drop(1). But it's a bit more convenient to leave the zero on the front (because then you always test the sum of list(n)-list(m) for n > m) — The Archetypal Paul

The Archetypal Paul The Archetypal Paul · Accepted Answer · 2015-04-05T09:38:00

val list:List[Int] = List(1, 4, 20, 3, 10, 5)
val sum = 33

A method to return a iterator of sublists, first with the ones that start with the first element, then starting with the second...

def subLists[T](xs:List[T]):Iterator[List[T]] =
     if (xs == Nil) Iterator.empty
     else xs.inits ++ subLists(xs.tail)

Find the first list with the correct sum

val ol = subLists(list).collectFirst{ case x if x.sum == sum => x}

Then find the index again, and print the result

ol match {
    case None => println("No such subsequence")
    case Some(l) => val i = list.indexOfSlice(l)
                println("Sequence of sum " + sum +
                        " found between " + i +
                         " and " + (i + l.length - 1))
} 
//> Sequence of sum 33 found between 2 and 4

(you could keep track of the index associated with the sublist when building the iterator, but that seems more trouble than it is worth, and reduces the general usefulness of subLists)

EDIT: Here's a version of the code you posted that's more "functional". But I think my first version is clearer - it's simpler to separate the concerns of generating the sequences from checking their sums

 val sumList = list.scanLeft(0){_ + _}
 val is = for {i <- 1 to list.length - 1
                j <- 0 to i
                if sumList(i)-sumList(j) == sum}
             yield (j, i-1)

 is match {
    case Seq() => println("No such subsequence")
    case (start, end) +: _ =>
                 println("Sequence of sum " + sum +
                         " found between " + start + " and " + end )
 } 
 //> Sequence of sum 33 found between 2 and 4

EDIT2: And here's an O(N) one. "Functional" in that there are no mutable variables, but it's less clear than the others, in my opinion. It's a bit clearer if you just print the results as they are found (no need to carry the rs part of the accumulator between iterations) but that side-effecting way seems less functional, so I return a list of solutions.

 val sums = list.scanLeft(0)(_ + _) zipWithIndex
 sums.drop(1).foldLeft((sums, List[(Int, Int)]())) {
    case ((leftTotal, rs), total) =>
      val newL = leftTotal.dropWhile(total._1 - _._1 > target)
      if (total._1 - newL.head._1 == target)
        (newL, (newL.head._2, total._2 - 1) :: rs)
      else (newL, rs)
  }._2
  //> res0: List[(Int, Int)] = List((2,4))

O(N) because we pass the shortened newL as the next iterations leftTotal, so dropWhile only ever goes through the list once. This one relies on the integers being non-negative (so adding another element cannot reduce the total), the others work with negative integers too.

Find subarray with given sum

1 Answers