5
\$\begingroup\$

I would really appreciate if you can help me to find a better way to do it.

public class SplitArray
{

    public SplitArray() { }


    public bool CanArrayBeSplit(int[] intArray)
    {          
        foreach(var pair in GeneratePairs(intArray))
        {
            if (pair.Item1 == pair.Item2)
                return true;
        }

        return false;
    }


    private List<Tuple<int, int>> GeneratePairs(int[] integerArray)
    {
        var output = new List<Tuple<int, int>>();
        for (int i = 0; i < integerArray.Length -1; i++)
        {
            output.Add(Tuple.Create(GetSum(0, i+1, integerArray), GetSum(i + 1, integerArray.Length ,integerArray)));
        }
        return output;
    }


    private int GetSum(int startIndex, int endIndex , int[] array)
    {
        int sum = 0;

        for (int i = startIndex; i < endIndex; i++)
        {
            sum += array[i];    
        }

        return sum;
    }
}
\$\endgroup\$
8
\$\begingroup\$

The solution to this problem is easy, once you know the trick.

The trick, is to calculate the sum of all values then do add/subtract until they match...

This is very different to what you have done, so it does not really make sense to review your algorithm, and then say 'you did it wrong'.

What I will do, is say your code is neat enough, and the logic you have done is visible enough, to make the algorithm clear. Even though it is not the best algorithm, you have implemented it well.

The problems with your algorithm are that you are doing the following:

  • you are calculating the sums of each side of the split each time
  • you are calculating all possible splits, even if you could identify a successful split sooner
  • The Pairs and other classes are overkill for the solution you could have....

So, the following code (on ideone too) makes the 'simple' solution 'obvious'....

public static bool CanArrayBeSplit(int[] intArray) {
    int sum = 0;
    foreach (int v in intArray) {
        sum += v;
    }
    int left = 0;
    int right = sum;
    for (int i = 0; left != right && i < intArray.Length; i++) {
        left += intArray[i];
        right -= intArray[i];
    }
    return left == right;
}
public static void Main()
{
    Console.WriteLine("Testing: " + CanArrayBeSplit(new int[]{1,2,3,4,5,6,7,8,9}));
    Console.WriteLine("Testing: " + CanArrayBeSplit(new int[]{1,2,3,4,5,6,7,8,9,45}));

}
\$\endgroup\$
  • \$\begingroup\$ Not the correct solution, will fail in so many cases, like {1,4,4,5,5,11}, which can be dividedinto {1,4,5,5} and {4,11}, but your solution will return false, here's a better solution - geeksforgeeks.org/dynamic-programming-set-18-partition-problem \$\endgroup\$ – Mrinal Kamboj Jan 6 '17 at 8:00
  • \$\begingroup\$ @MrinalKamboj - I believe you have misunderstood the problem being solved. The objective is to "split" the array at a specific index, where the sum of the elements on one side of the index matches the sum on the other side. You are not splitting though, you are instead seeking one subset of the elements that matches the sum of the remainder of the elements, where the subset consists of any elements, not just the left-most elements. My code above solves a simple "split" just fine, but you are right, it is not designed, nor will it work, to solve a non sequential subset. \$\endgroup\$ – rolfl Jan 6 '17 at 13:42
  • \$\begingroup\$ Thanks for the clarification, then I am looking for a different solution \$\endgroup\$ – Mrinal Kamboj Jan 9 '17 at 9:07
7
\$\begingroup\$
  1. You do not need to re-caclcute sum on every iteration in your GeneratePairs() method. You can simply create two varaibles which would hold the sums of two "sides" of your array. Then on every iteration you can simply add the item value to the first variable and subtract it from second. You can use IEnumerable.Sum() method to get the initial sum value for "right side".
  2. I see no reason to keep splitting the array once you have found the split index. You should probably merge CanArrayBeSplit and GeneratePairs methods into one to fix this issue. You can avoid creating pairs this way as well (i think they are not needed here).
  3. If you want to actually split an array you should probably store (or return) the split index as well somehow.
  4. Your class can be made static.
\$\endgroup\$
2
\$\begingroup\$

The answer by rolfl works under the assumption that the array may only contain non-negative integers.

If the restriction is integers >= 0, then the for conditional could be short-circuited to:

left < right && i < intArray.Length

If the array can contain negative numbers, then there is a corner case where rolfl's code would may produce the wrong results: if the initial sum of the array is 0, in which case the for loop will never iterate. Again another nit-picky assumption is that splitting somewhere along the original array would produce 2 non-empty arrays. Otherwise if the sum is 0, you may 'split' on the original array and an empty array.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.