Snippets Collections
// A Java program to find
// if there is a zero sum subarray
import java.util.HashSet;
import java.util.Set;

class ZeroSumSubarray
{
	// Returns true if arr[]
	// has a subarray with sero sum
	static Boolean subArrayExists(int arr[])
	{
		// Creates an empty hashset hs
		Set<Integer> hs = new HashSet<Integer>();

		// Initialize sum of elements
		int sum = 0;

		// Traverse through the given array
		for (int i = 0; i < arr.length; i++)
		{
			// Add current element to sum
			sum += arr[i];

			// Return true in following cases
			// a) Current element is 0
			// b) sum of elements from 0 to i is 0
			// c) sum is already present in hash map
			if (arr[i] == 0
				|| sum == 0
				|| hs.contains(sum))
				return true;

			// Add sum to hash set
			hs.add(sum);
		}

		// We reach here only when there is
		// no subarray with 0 sum
		return false;
	}

	// Driver code
	public static void main(String arg[])
	{
		int arr[] = { -3, 2, 3, 1, 6 };
		if (subArrayExists(arr))
			System.out.println(
				"Found a subarray with 0 sum");
		else
			System.out.println("No Such Sub Array Exists!");
	}
}
// Java program to determine if array arr[]
// can be split into three equal sum sets.

// Time Complexity: O(n), Auxiliary Space: O(1)

import java.io.*;
import java.util.*;

public class GFG {
	
	// Function to determine if array arr[]
	// can be split into three equal sum sets.
	static int findSplit(int []arr, int n)
	{
		int i;
	
		// variable to store prefix sum
		int preSum = 0;
	
		// variables to store indices which
		// have prefix sum divisible by S/3.
		int ind1 = -1, ind2 = -1;
	
		// variable to store sum of
		// entire array.
		int S;
	
		// Find entire sum of the array.
		S = arr[0];
		for (i = 1; i < n; i++)
			S += arr[i];
	
		// Check if array can be split in
		// three equal sum sets or not.
		if(S % 3 != 0)
			return 0;
		
		// Variables to store sum S/3
		// and 2*(S/3).
		int S1 = S / 3;
		int S2 = 2 * S1;
	
		// Loop until second last index
		// as S2 should not be at the last
		for (i = 0; i < n-1; i++)
		{
			preSum += arr[i];
			
		// If prefix sum is equal to S/3
		// store current index.
			if (preSum == S1 && ind1 == -1)
				ind1 = i;
			
		// If prefix sum is equal to 2*(S/3)
		// store current index.
			else if(preSum == S2 && ind1 != -1)
			{
				ind2 = i;
				
				// Come out of the loop as both the
				// required indices are found.
				break;
			}
		}
	
		// If both the indices are found
		// then print them.
		if (ind1 != -1 && ind2 != -1)
		{
			System.out.print("(" + ind1 + ", "
							+ ind2 + ")");
			return 1;
		}
	
		// If indices are not found return 0.
		return 0;
	}
	
	// Driver code
	public static void main(String args[])
	{
		int []arr = { 1, 3, 4, 0, 4 };
		int n = arr.length;
		if (findSplit(arr, n) == 0)
			System.out.print("-1");
	}
}

// Output: (1, 2)
star

Mon Feb 07 2022 15:44:47 GMT+0000 (UTC) https://www.geeksforgeeks.org/find-if-there-is-a-subarray-with-0-sum/

#java #gfg #geeksforgeeks #lecture #arrays #prefixsum #subarrays #splitarray
star

Mon Feb 07 2022 15:33:54 GMT+0000 (UTC) https://www.geeksforgeeks.org/split-array-three-equal-sum-subarrays/

#java #gfg #geeksforgeeks #lecture #arrays #prefixsum #subarrays #splitarray

Save snippets that work with our extensions

Available in the Chrome Web Store Get Firefox Add-on Get VS Code extension