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

Asked 2009-07-15T16:06:18.307

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

algorithm puzzle

Edit Report

2 Answers

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


                        
                        
                            answered 2009-07-15T16:29:50.880


            
            
                
                    
                        
                            
                            
                        
                        0
                        
                            
                            
                        
                        
                    
                    
                        
                        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));


                        
                        
                            answered 2009-07-15T16:31:22.873



        
        
            Your Answer