How to optimally divide an array into two subarrays so that sum of elements in both are same ?

There are two methods used to split arrays,

  • Given an array of integers greater than zero, find if it is possible to split it in two subarrays (without reordering the elements), such that the sum of the two subarrays is the same. For example,
Input : Arr[] = { 1 , 2 , 3 , 4 , 5 , 5  }
Output :  { 1 2 3 4 } 
          { 5 , 5 }
  • Given an array of integers, find if it’s possible to remove exactly one integer from the array that divides the array into two subarrays with the same sum. For Example,
                           Input:  arr = [6, 2, 3, 2, 1]
                           Output:  true
  • On removing element 2 at index 1, the array gets divided into two subarrays [6] and [3, 2, 1] having equal sum.

Sample Code in Java

/ Java program to split an array 
// into two equal sum subarrays 
import java.io.*;

class Wikitechy {

    // Returns split point. If 
    // not possible, then return -1. 
    static int findSplitPoint(int arr[], int n) {

        int leftSum = 0;

        // traverse array element 
        for (int i = 0; i < n; i++) {
            // add current element to left Sum 
            leftSum += arr[i];

            // find sum of rest array 
            // elements (rightSum) 
            int rightSum = 0;

            for (int j = i + 1; j < n; j++)
                rightSum += arr[j];

            // split point index 
            if (leftSum == rightSum)
                return i + 1;
        }

        // if it is not possible to 
        // split array into two parts 
        return -1;
    }

    // Prints two parts after finding 
    // split point using findSplitPoint() 
    static void printTwoParts(int arr[], int n) {

        int splitPoint = findSplitPoint(arr, n);

        if (splitPoint == -1 || splitPoint == n) {
            System.out.println("Not Possible");
            return;
        }

        for (int i = 0; i < n; i++) {
            if (splitPoint == i)
                System.out.println();

            System.out.print(arr[i] + " ");

        }
    }

    // Driver program 

    public static void main(String[] args) {

        int arr[] = {1,1,0,2};
        int n = arr.length;
        printTwoParts(arr, n);

    }
}

Output

1 1 
0 2

Categorized in:

Java

Tagged in:

, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,