In the previous article, we have seen Java Program to Count Strings and Integers from an Array
In this article we are going to see how to find continuous sub array whose sum is equal to given number.
Java Program to Find Continuous Sub array Whose Sum is Equal to a Given Number
Array is a data structure which stores a fixed size sequential collection of values of single type. Where with every array elements/values memory location is associated. Each array elements have it’s own index where array index starts from 0.
In Array set of variables referenced by a single variable name and it’s array index position. It is also called as a container object which contains elements of similar type.
Declaration of an array:
dataType[] arrayName; (or) //Declaring an array dataType []arrayName; (or) dataType arr[];
Instantiation of an Array:
arrayName = new datatype[size]; //Allocating memory to array
Combining both Statements in One:
dataType[] arrayName = new dataType[size] //Declaring and Instantiating array
Initialization of an Array:
arrayName[index-0]= arrayElement1 //Initializing the array ... arrayName[index-s]= arrayElementS
Combining all Statements in One:
dataType arrayName[ ]={e1,e2,e3}; //declaration, instantiation and initialization
Let’s see different ways to find continuous sub array whose sum is equal to given number.
Method-1: Java Program to Find Continuous Sub array Whose Sum is Equal to a Given Number By Static Initialization of Array Elements
Approach:
- Initialize the sum to first element of the
inputArray. - Starting from the second element, go on adding each element of
inputArrayto sum one by one. - If the sum exceeds the
requiredSumthen we remove starting elements from the sum until sum becomes either smaller than or equal to therequiredSum. - If sum becomes equal to
requiredSumthen print that sub array. - If sum becomes smaller than
requiredSum, then we continue the execution of loop.
Program:
import java.util.Arrays;
public class Main
{
public static void main(String[] args)
{
int[] arr = { 27, 5, 3, 80, 7, 9, 12 };
int requiredSum = 95;
findSubArray(arr, requiredSum);
}
static void findSubArray(int[] arr, int requiredSum)
{
// Initializing sum with the first element of the inputArray
int sum = arr[0], start = 0;
// Iterating through inputArray starting from second element
for (int i = 1; i < arr.length; i++)
{
// Adding inputArray[i] to the current 'sum'
if (sum == requiredSum) {
System.out.print("Continuous sub array of " + Arrays.toString(arr) + " whose sum is "
+ requiredSum + " is [ ");
for (int j = start; j < i; j++)
{
// If 'sum' is equal to 'requiedSum' then printing the sub array
System.out.print(arr[j] + " ");
}
System.out.println("]");
}
sum = sum + arr[i];
// If sum is greater than requiedSum then following loop is executed until
// sum becomes either smaller than or equal to requiedSum
while (sum > requiredSum && start <= i - 1)
{
// Removing starting elements from the 'sum'
sum = sum - arr[start];
// Incrementing start by 1
start++;
}
}
}
}
Output: Continuous sub array of [27, 5, 3, 80, 7, 9, 12] whose sum is 95 is [ 5 3 80 7 ]
Method-2: Java Program to Find Continuous Sub array Whose Sum is Equal to a Given Number By Dynamic Initialization of Array Elements
Approach:
- Create scanner class object.
- Ask use length of the array.
- Initialize the array with given size.
- Ask the user for array elements.
- Initialize sum variable with arr[0].
- Run two nested loops and try out every possible continuous subarray.
- Inside the inner loop(counter j) increment sum by the jth element of the array.
- Check if the
sum==requiredSum. - If yes, print the subarray.
- If it’s greater then break the inner loop and if less then continue the current execution.
Program:
import java.util.Arrays;
import java.util.Scanner;
public class Main
{
public static void main(String[] args)
{
// create scanner class object
Scanner sc = new Scanner(System.in);
// take input from user for array size
System.out.print("Enter the size of array: ");
int n = sc.nextInt();
// initialize array with size n
int[] arr = new int[n];
// take input from user for array elements
System.out.print("Enter array elements: ");
for (int i = 0; i < n; i++)
{
arr[i] = sc.nextInt();
}
System.out.print("Enter the required sum: ");
int requiredSum = sc.nextInt();
findSubArray(arr, requiredSum);
}
static void findSubArray(int[] arr, int requiredSum)
{
// Initializing 'sum' to 0
int sum = 0;
// Iterating through 'inputArray'
for (int i = 0; i < arr.length; i++)
{
// Assigning inputArray[i] to 'sum'
sum = arr[i];
for (int j = i + 1; j < arr.length; j++)
{
// Adding inputArray[j] to 'sum'
sum = sum + arr[j];
// If 'sum' is equal to 'inputNumber' then printing the sub array
if (sum == requiredSum)
{
System.out.print("Continuous sub array of " + Arrays.toString(arr) + " whose sum is "
+ requiredSum + " is [ ");
for (int k = i; k <= j; k++)
{
System.out.print(arr[k] + " ");
}
System.out.println("]");
}
// if 'sum' is smaller than 'inputNumber', continue the loop
else if (sum < requiredSum)
{
continue;
}
// if 'sum' is greater than 'inputNumber', then break the loop
else if (sum > requiredSum)
{
break;
}
}
}
}
}
Output: Enter the size of array: 6 Enter array elements: 7 2 5 3 1 4 Enter the required sum: 9 Continuous sub array of [7, 2, 5, 3, 1, 4] whose sum is 9 is [ 7 2 ] Continuous sub array of [7, 2, 5, 3, 1, 4] whose sum is 9 is [ 5 3 1 ]
Practice Java programming from home without using any fancy software just by tapping on this Simple Java Programs for Beginners tutorial.
Related Java Programs: