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
Hence, Find the sum of all the elements of the array. If the sum is odd, the array cannot be partitioned into two subarrays having equal sums. If the sum is even, divide the array into subsets, such that both have sums equal to sum/2.
A Simple solution is to run two loop to split array and check it is possible to split array into two parts such that sum of first_part equal to sum of second_part. Below is the implementation of above idea.
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]
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
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:
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With