WAP to Split An Array Into Two Equal Sum Subarrays

by

Split An Array Into Two Equal Sum Subarrays: This Java program aims to solve a problem involving dividing an integer array into two subarrays at a specific index, where the sum of elements in both subarrays is equal. Let’s break down the program step by step for beginners:

Split Array Into Two Equal Sum Subarrays

package com.softwaretestingo.interviewprograms;
public class InterviewPrograms98 
{
	// This Questions Asked In Unify technologies
	//Suppose this is interger array (2,3,4,1,4,5) divide this array into from the index of 
	//that element where sum is equal for both divided arrays for eg:- 
	//1 in this case should be printed as sum of both int arrays (2,3,4) and (4,5) is 9
	public static void main(String[] args) 
	{
		int a[] = {2,3,4,1,4,5};
		int sum1=0;
		int sum2=0;
		int ans=0;
		for (int i = 0; i<=a.length-1; i++) 
		{
			sum1=sum1+a[i];
			for (int j = i+2; j<=a.length-1; j++) 
			{
				sum2=sum2+a[j];
			}
			if(sum1==sum2)
			{
				ans=a[i+1];
			}
			sum2=0;
		}
		System.out.print(ans);
	}
}

Output:

1

Problem Description: The program addresses a scenario where you have an integer array, such as {2, 3, 4, 1, 4, 5}. The goal is to find an index ‘i’ such that the sum of elements in the subarray {2, 3, …, a[i]} is equal to the sum of elements in the subarray {a[i+1], a[i+2], …, a[n-1]}.

Main Method: The program starts by defining a class named InterviewPrograms98 and the main method within it.

Array Initialization: An integer array ‘a’ is initialized with values {2, 3, 4, 1, 4, 5}.

Initialization: Three integer variables are defined: sum1 (initially 0) to track the sum of the left subarray, sum2 (initially 0) to track the sum of the right subarray, and ans (initially 0) to store the answer.

Outer Loop: The program enters a loop that iterates through the elements of the array using the variable ‘i’. The loop’s purpose is to consider different indices as the potential splitting point between subarrays.

Left Subarray Sum: Inside the outer loop, the program increments the sum1 by adding the value of the current element a[i] to it. This is effectively calculating the sum of elements in the left subarray.

Inner Loop: Within the outer loop, there’s an inner loop that starts from the index ‘i+2’ and iterates till the end of the array using variable ‘j’. This loop calculates the sum of elements in the right subarray (starting from a[i+1] onwards).

Check for Equal Sums: After calculating the sum of both subarrays, the program checks if sum1 (left subarray sum) is equal to sum2 (right subarray sum). If they are equal, it means the division point is found, and the element a[i+1] is stored in the variable ans.

Reset Right Subarray Sum: The sum2 variable is reset to 0 for the next iteration of the outer loop.

Print Result: Once the loop completes, the program prints the value of the ans variable, which represents the element that divides the array into two subarrays with equal sums.

In summary, this program solves the problem of finding an index in an integer array where the sum of elements on both sides of the index is equal. It employs nested loops to calculate these sums and then determines the desired index.

Alternative Way 1:

This Java program aims to find a split point in an array where the sum of the elements on the left side of the split point is equal to the sum of the elements on the right side. In other words, it tries to determine if the array can be divided into two parts with equal sums.

package com.softwaretestingo.interviewprograms;
public class InterviewPrograms98_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] + " ");

		}
	}

	public static void main(String[] args) 
	{
		int arr[] = {1 , 2 , 3 , 4 , 5 , 5 };
		int n = arr.length;
		printTwoParts(arr, n);
	}
}

Output:

1 2 3 4 
5 5

Here’s a step-by-step explanation of the given program for Java beginners:

  • The program defines a class named InterviewPrograms98_1.
  • Inside the class, there’s a method findSplitPoint that takes an integer array arr and its length n as parameters. It searches for a split point where the sum of elements on the left side equals the sum of elements on the right side.
  • It initializes leftSum to 0, which will store the cumulative sum of elements on the left side of the split point.
  • The program uses a loop to iterate through the array’s elements. In each iteration, it adds the current element’s value to leftSum.
  • Inside the same loop, there’s a nested loop to calculate the sum of the elements on the right side of the split point. The rightSum is calculated by iterating through the array’s remaining elements starting from the next index.
  • If leftSum equals rightSum, it means a split point has been found where the array can be divided into two parts with equal sums, and the loop returns the split point index (i+1).
  • If the loop completes without finding such a split point, the method returns -1 to indicate that the array cannot be split in the desired way.
  • Another method, printTwoParts, takes the same array arr and length n. It uses the findSplitPoint method to get the split point.
  • If splitPoint is -1 or equal to n, it means no valid split point was found, and the program prints “Not Possible” and returns.
  • The program then prints the two parts of the array separated by the split point. It iterates through the array, and when the index matches the splitPoint, it prints a newline to separate the two parts.
  • Finally, the main method is defined, where an example integer array arr is created. The length of the array n is calculated using arr.length, and the printTwoParts method is called to find and display the split parts of the array.

In short, this program checks if an array can be divided into two parts with equal sums and displays those parts if possible.

Alternative Way 2:

A more effective strategy is to begin by calculating the sum of the entire array in a left-to-right manner. Subsequently, we iterate through the array in reverse, simultaneously monitoring the sum on the right side. The sum on the left side can be derived by deducting the present element from the overall sum.

package com.softwaretestingo.interviewprograms;
public class InterviewPrograms98_2 
{

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

		// traverse array element and compute sum
		// of whole array
		int leftSum = 0;

		for (int i = 0 ; i < n ; i++)
			leftSum += arr[i];

		// again traverse array and compute right 
		// sum and also check left_sum equal to 
		// right sum or not
		int rightSum = 0;

		for (int i = n-1; i >= 0; i--)
		{
			// add current element to right_sum
			rightSum += arr[i];

			// exclude current element to the left_sum
			leftSum -= arr[i] ;

			if (rightSum == leftSum)
				return i ;
		}

		// 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] + " ");
		}
	}
	public static void main(String[] args) 
	{
		int arr[] = {1 , 2 , 3 , 4 , 5 , 5 };
		int n = arr.length;

		printTwoParts(arr, n);
	}
}

Output:

1 2 3 4 
5 5

This java program language aims to determine a split point within an array where the sum of elements on the left side is equal to the sum of elements on the right side. Essentially, the program is trying to identify whether the given array can be divided into two parts with equivalent sums.

Here’s a beginner-friendly, step-by-step explanation of the provided code:

  • The program defines a class named InterviewPrograms98_2.
  • Inside the class, there’s a method named findSplitPoint that takes an integer array arr and its length n as parameters. This method searches for a point where the array can be divided into two parts with equal sums.
  • It initializes leftSum to 0, which will store the cumulative sum of elements on the left side of the potential split point.
  • The program employs a loop to iterate through the array’s elements from left to right. In each iteration, the current element’s value is added to leftSum.
  • After the initial loop, another loop is used to traverse the array in reverse (from right to left). Inside this loop, the program calculates the sum on the right side of the potential split point by adding the current element’s value to rightSum. Simultaneously, the value of the current element is subtracted from leftSum.
  • If at any point rightSum equals leftSum, it means a valid split point has been found, and the loop returns the index i.
  • If the loop completes without finding a valid split point, the method returns -1 to indicate that the array cannot be split in the desired manner.
  • Another method, printTwoParts, is defined to take an integer array arr and its length n. This method uses the findSplitPoint function to determine the split point.
  • If splitPoint is -1 or equal to n, it means no valid split point was found. In this case, the program prints “Not Possible” and returns.
  • The program then prints the two parts of the array separated by the split point. It iterates through the array, and when the index matches the splitPoint, it prints a newline to separate the two parts.
  • Finally, the main method is defined, where an example integer array arr is created. The length of the array n is calculated using arr.length, and the printTwoParts method is called to determine and display the split parts of the array.

In summary, this program checks if an array can be divided into two parts with equal sums and displays those parts if a valid split point exists.

I love open-source technologies and am very passionate about software development. I like to share my knowledge with others, especially on technology that's why I have given all the examples as simple as possible to understand for beginners. All the code posted on my blog is developed, compiled, and tested in my development environment. If you find any mistakes or bugs, Please drop an email to softwaretestingo.com@gmail.com, or You can join me on Linkedin.

Leave a Comment