recursion: cut array of integers in two parts of equal sum - in a single pass

Question

Using recursion, find an index that cuts an array in two parts so that both parts have equal sum.

Cut means to cut like with a knife. All the cells with index <= to the result must be equal in their sum to the all the cells with index > to the result. No cells can be left off or be part of both sides.

The arrays contains arbitrary integers (i.e. positives, negatives, and zeros).

If there is no such index return -1.

You are not allowed to allocate heap objects.

You must do it in a single pass.

You must do it with recursion (i.e. cannot use loop constructs).

Can be in any language or pseudocode.

Forgot to add this: You cannot modify the array

Answer 1

Iterating with recursion is a trivial transformation, so we'll assume you know how to do that.

If you use your "one pass" to build your own array of "sum to this index", and can make another pass on that array, I could see how to do it. Just iterate through that second array and subtract sum[x] from sum[last]. If you ever find a situation where the result = sum[x] you return x. If you don't then return -1.

As Neil N mentioned, if you define "pass" very loosely for recursion, such that the entire recursion can actually visit indices multiple times, then you could dispense with the second array.

---

After thinking about this a bit, I suspect the idea is to get you to only visit every array element once (in order), and to use recursion's built-in stack property to get rid of the need for any second array.

What you do is write your recursive routine to save off it's current index's array value in a local, add that value to a passed in "sum_of_array" value, then call itself on the next highest index (if there is one). If there isn't a next highest index, it saves the sum into a global, which is now available to every stacked recursive call. Each routine finishes by checking its sum against the global sum. If it is half, then it returns its index. Otherwise it returns -1. If a non -1 was returned from a call to itself, this last step is skipped and that value is returned. I'll show in pseudo-Ada

Total_Sum : integer;

function Split (Subject : Integer_Array; After : Integer := 0; Running_Sum : Integer := 0) is
begin
   Running_Sum := Running_Sum + Subject(After);
   if (After < Subject'last) then --'// comment Hack for SO colorizer
      Magic_Index : constant Integer := Split (Subject, After +  1, Running_Sum);
      if (Magic_Index = -1) then
         if (Total_Sum - Running_Sum = Running_Sum) then
            return After;
         else
            return -1;
         end if;
      else
         return Magic_Index;
      end if;
   else
      Total_Sum := Running_Sum;
      return -1;
   end if;
end Split;

This code should have the properties that:

• Calling it with just an array will return the described "split" index, or -1 if there isn't one.
• It only reads from any element in the source array once
• It reads the source array elements in strict index order.
• No extra structured data storage (array) is required.

Answer 2

public static Int32 SplitIndex(Int32[] array, Int32 left, Int32 right, Int32 leftsum, Int32 rightsum)
{
    if (left == right - 1)
    {
        return (leftsum == rightsum) ? left : -1;
    }

    if (leftsum > rightsum)
    {
        return SplitIndex(array, left, right - 1, leftsum, rightsum + array[right - 1]);
    }
    else
    {
        return SplitIndex(array, left + 1, right, leftsum + array[left + 1], rightsum);
    }
}

The method is called as follows.

Int32[] a = { 1, 2, 3, 1, 6, 1 };

Console.WriteLine(SplitIndex(a, -1, a.Length, 0, 0));

This can be reduced to use only a single sum and targeting zero.

public static Int32 SplitIndex(Int32[] array, Int32 left, Int32 right, Int32 sum)
{
    if (left == right - 1)
    {
        return (sum == 0) ? left : -1;
    }

    if (sum > 0)
    {
        return SplitIndex(array, left, right - 1, sum - array[right - 1]);
    }
    else
    {
        return SplitIndex(array, left + 1, right, sum + array[left + 1]);
    }
}

The method is now called as follows.

Int32[] a = { 1, 2, 3, 1, 6, 1 };

Console.WriteLine(SplitIndex(a, -1, a.Length, 0));

Answer 3

Take a look at the following, using only 1 index, assume array's indexes are 1-based:

int recursion(index, rightvalue, leftvalue, array)
{
if array=[] then
{
    if rightvalue=leftvalue then return index
    else return -1
}
else
{
    if rightvalue <= leftvalue
    { recursion(index+1, rightvalue+array[1], leftvalue, array[2..len(array)] }
    else 
    { recursion(index, rightvalue, leftvalue+array[len(array)], array[1..len(array)-1] }
}

int main_function(array)
{
    return recursion(1, 0, 0, array)
}

Answer 4

Here's a way to do it that takes advantage of Ruby's ability to return multiple values. The first value is the index for the split (if it exists), the second is the sum of each half (or the sum of the whole array if no split is found):

def split(arr, index = 0, sum = 0)
  return -1, arr[index] if index == arr.length - 1
  sum = sum + arr[index]
  i, tail = split(arr, index + 1, sum)

  if i > -1
    return i, tail
  elsif sum == tail
    return index, sum 
  end
  return -1, arr[index] + tail
end

Calling it like this:

p split([1, 1, 2])
p split([1])
p split([-1, 2, 1])
p split([2, 3, 4])
p split([0, 5, 4, -9])

Results in this:

[1, 2]
[-1, 1]
[1, 1]
[-1, 9]
[0, 0]

EDIT:

---

Here's a slightly modified version to address onebyone.livejournal.com's comments. Now each index in the array is accessed only once:

def split(arr, index = 0, sum = 0)
  curr = arr[index]
  return -1, curr if index == arr.length - 1
  sum = sum + curr
  i, tail = split(arr, index + 1, sum)

  if i > -1
    return i, tail
  elsif sum == tail
    return index, sum 
  end
  return -1, curr + tail
end

Answer 5

Pseudo-code

def cut(array, leftsum, depth)
    if array.isempty return 0
    value = array.shift // or whatever pointer manipulation you like
    leftsum += value
    rightsum = cut(array, leftsum, depth+1);
    if (leftsum == rightsum) throw(depth + 1)
    return rightsum + value

def find_cut
    try
        if cut(array, 0, 0) == 0
            result = 0
        else
            result = -1
    catch e
        result = e
    return result

Obviously the "throw" stuff can be done with with a magic return value that's checked on each call and propagated upwards, or by returning a pair, or whatever is appropriate for the language.

Note that I don't consider "array.shift" to count as modifying the array, because the purpose of removing the value is just to "prove" that only a single pass is required: if I remove each value as I read it, then I can hardly read it twice. In C you would just advance a pointer forward over the array, and the "shift" operation would be *(p++).

Answer 6

My version:

# Returns either (right sum from the currentIndex, currentIndex, False),
# or, if the winning cut is found, (sum from the cut, its index, True)
def tryCut(anArray, currentIndex, currentLeftSum):
   if currentIndex == len(anArray):
      return (0, currentIndex, currentLeftSum==0)

   (nextRightSum, anIndex, isItTheWinner) = tryCut(anArray, currentIndex + 1, currentLeftSum + anArray[currentIndex])

   if isItTheWinner: return (nextRightSum, anIndex, isItTheWinner)
   rightSum = anArray[currentIndex] + nextRightSum
   return (rightSum, currentIndex, currentLeftSum == rightSum)

def findCut(anArray):
   (dummy, anIndex, isItTheWinner) = tryCut(anArray, 0, 0)
   if isItTheWinner: return anIndex
   return -1

Note: if the index returned is 5, I mean that sum(anArray[:5]) == sum(anArray[5:]). The "extremes" are also valid (where the sum of an empty slice is meant to be zero), i.e. if the sum of the whole array is zero, then 0 and len(anArray) are also valid cuts.

Answer 7

Code in C/C++/Java:

function cut(int i, int j, int s1, int s2, int a[])
{
    if(i==j && s1==s2)
        return i;
    else if(i==j && s1!=s2)
        return -1;
    else if(s1>s2)
        return cut(i, j-1, s1, s2 + a[j-1]);
    else
        return cut(i+1, j, s1 + a[i+1], s2);
}

Call using the following syntax:

cut(0, array.length, 0, 0, array);

Answer 8

Here's an implementation in Erlang, since I'm learning it and this seemed like an interesting challenge. Idea shamelessly cribbed from Pesto's solution.

find_split(List) -> {Idx, _Sum} = find_split(List, 1, 0), Idx.
find_split([Head], _Idx, _Sum) -> {-1, Head};
find_split([Head|Tail], Idx, Sum) ->
  case find_split(Tail, Idx + 1, Sum + Head) of
    {-1, Tailsum} when Sum + Head == Tailsum -> {Idx, Sum + Head};
    {-1, Tailsum} -> {-1, Head + Tailsum};
    Ret -> Ret
  end.

Answer 9

Haskell:

split' _ s [] = (-1, s)
split' idx s (x:xs) | sidx >= 0   = (sidx, s')
                    | s * 2 == s' = (idx - 1, s)
                    | otherwise   = (-1, s')
    where (sidx, s') = split' (idx + 1) (x + s) xs

split = fst . split' 0 0

Your rules are somewhat misleading. You require that no objects are to be allocated on the heap, but IMHO there is no solution where the algorithm does not have space requirements of O(n), i.e. the stack grows linearly with the length of the list and tail calls are not possible because the function has to inspect the return values from the recursive call.