Count subarray with given sum
The problem of counting subarrays with a given sum is a classic algorithmic challenge. Given an array of integers and a target sum, the task is to find the total number of subarrays within the array that add up to the given sum. This problem has applications in various domains, including financial analysis, data processing, and more. In this article, we will delve into the problem statement, provide a detailed explanation using suitable examples, present an approach to solve it, provide the pseudocode and algorithm with explanations, discuss the resultant output, and analyze the time complexity of the solution.
Problem Statement and Description
Imagine you have an array of integers like this: [-10, 23, 7, -18, 11, 9, 4, -4, 8, -17], and
you're given a target sum, say 13. The problem is to find out how many contiguous subarrays within this array
add up to the given sum of 13. Subarrays are essentially segments of the array, where the order of elements is
preserved. For instance, in the given example, there are five subarrays that sum up to 13:
[23, 7, -18, 11], [7, -18, 11, 9, 4], [11, 9, 4, -4, 8],
[4, -4, 8, -17], and [9, 4].
Idea to Solve the Problem
To solve this problem, we need to iterate through the array and consider all possible subarrays. For each subarray, we calculate the sum and compare it with the given target sum. If they match, we increment a counter. By considering all possible subarrays, we can determine the total count of subarrays that satisfy the given sum condition.
Pseudocode
Here's the pseudocode for the algorithm:
subarray_sum(array, size, sum)
result = 0
for i = 0 to size - 1
auxiliary = array[i]
for j = i + 1 to size - 1
auxiliary += array[j]
if auxiliary == sum
result++
print "Total subarrays of sum [", sum, "] is:", result
main()
collection = [-10, 23, 7, -18, 11, 9, 4, -4, 8, -17]
size = size of collection
subarray_sum(collection, size, 13)
subarray_sum(collection, size, 9)Algorithm Explanation
- Start by initializing the
resultcounter to 0. - Outer loop iterates over each index 'i' in the array.
- Initialize an
auxiliaryvariable with the value at index 'i'. - Inner loop iterates from index 'i+1' to the end of the array.
- In each iteration of the inner loop, add the current element to the
auxiliarysum. - Check if the
auxiliarysum is equal to the givensum. If it is, increment theresultcounter. - Finally, print the total count of subarrays that match the given sum for the current test case.
Code Solution
//C Program
//Count subarray with given sum
#include <stdio.h>
//Counting all subarrays of given sum in array
void subarray_sum(int collection[],int size,int sum)
{
if(size<=0)
{
//When array are no elemnts
return ;
}
//This result variables are using to store information about subarray sum pairs
int result = 0;
long long auxiliary=0;
for (int i = 0; i < size; ++i)
{
auxiliary = collection[i];
for (int j = i+1; j < size; ++j)
{
auxiliary += collection[j];
if(auxiliary==sum)
{
result++;
}
}
}
printf("Total subarray of sum [%d] is : %d\n",sum,result);
}
int main()
{
//Define array elements
int collection[]={ -10, 23, 7, -18, 11, 9, 4, -4, 8,-17 };
//Get the size of array
int size = sizeof(collection)/sizeof(collection[0]);
//Test Case
subarray_sum(collection,size,13);
subarray_sum(collection,size,9);
return 0;
}
Output
Total subarray of sum [13] is : 5
Total subarray of sum [9] is : 3/*
C++ Program
Count subarray with given sum
*/
#include<iostream>
using namespace std;
class MyArray {
public:
//Counting all subarrays of given sum in array
void subarray_sum(int collection[], int size, int sum) {
if (size <= 0) {
return;
}
//This result variables are using to store information about subarray sum pairs
int result = 0;
long auxiliary = 0;
for (int i = 0; i < size; ++i) {
auxiliary = collection[i];
for (int j = i + 1; j < size; ++j) {
auxiliary += collection[j];
if (auxiliary == sum) {
result++;
}
}
}
cout << "Total subarray of sum [" << sum << "] is : " << result << "\n";
}
};
int main() {
MyArray obj ;
//Define array elements
int collection[] = {
-10,
23,
7,
-18,
11,
9,
4,
-4,
8,
-17
};
//Get the size of array
int size = sizeof(collection) / sizeof(collection[0]);
//Test Case
obj.subarray_sum(collection, size, 13);
obj.subarray_sum(collection, size, 9);
return 0;
}
Output
Total subarray of sum [13] is : 5
Total subarray of sum [9] is : 3/*
Java Program
Count subarray with given sum
*/
public class MyArray {
//Counting all subarrays of given sum in array
public void subarray_sum(int []collection,int size,int sum)
{
if(size<=0)
{
//When array are no elemnts
return ;
}
//This result variables are using to store information about subarray sum pairs
int result = 0;
long auxiliary=0;
for (int i = 0; i < size; ++i)
{
auxiliary = collection[i];
for (int j = i+1; j < size; ++j)
{
auxiliary += collection[j];
if(auxiliary==sum)
{
result++;
}
}
}
System.out.print("Total subarray of sum ["+sum+"] is : "+result+"\n");
}
public static void main(String[] args)
{
MyArray obj = new MyArray();
//Define array elements
int collection[]={ -10, 23, 7, -18, 11, 9, 4, -4, 8,-17 };
//Get the size of array
int size=collection.length;
//Test Case
obj.subarray_sum(collection,size,13);
obj.subarray_sum(collection,size,9);
}
}
Output
Total subarray of sum [13] is : 5
Total subarray of sum [9] is : 3/*
C# Program
Count subarray with given sum
*/
using System;
public class MyArray {
//Counting all subarrays of given sum in array
public void subarray_sum(int[] collection, int size, int sum) {
if (size <= 0) {
return;
}
//This result variables are using to store information about subarray sum pairs
int result = 0;
long auxiliary = 0;
for (int i = 0; i < size; ++i) {
auxiliary = collection[i];
for (int j = i + 1; j < size; ++j) {
auxiliary += collection[j];
if (auxiliary == sum) {
result++;
}
}
}
Console.Write("Total subarray of sum [" + sum + "] is : " + result + "\n");
}
public static void Main(String[] args) {
MyArray obj = new MyArray();
//Define array elements
int []collection = {
-10,
23,
7,
-18,
11,
9,
4,
-4,
8,
-17
};
//Get the size of array
int size = collection.Length;
obj.subarray_sum(collection, size, 13);
obj.subarray_sum(collection, size, 9);
}
}
Output
Total subarray of sum [13] is : 5
Total subarray of sum [9] is : 3<?php
/*
Php Program
Count subarray with given sum
*/
class MyArray {
//Counting all subarrays of given sum in array
public function subarray_sum($collection, $size, $sum) {
if ($size <= 0) {
return;
}
//This result variables are using to store information about subarray sum pairs
$result = 0;
$auxiliary = 0;
for ($i = 0; $i < $size; ++$i) {
$auxiliary = $collection[$i];
for ($j = $i + 1; $j < $size; ++$j) {
$auxiliary += $collection[$j];
if ($auxiliary == $sum) {
$result++;
}
}
}
echo("Total subarray of sum [". $sum ."] is : ". $result ."\n");
}
}
function main() {
$obj = new MyArray();
//Define array elements
$collection = array(-10, 23, 7, -18, 11, 9, 4, -4, 8, -17);
//Get the size of array
$size = count($collection);
//Test Case
$obj->subarray_sum($collection, $size, 13);
$obj->subarray_sum($collection, $size, 9);
}
main();
Output
Total subarray of sum [13] is : 5
Total subarray of sum [9] is : 3/*
Node Js Program
Count subarray with given sum
*/
class MyArray {
//Counting all subarrays of given sum in array
subarray_sum(collection, size, sum) {
if (size <= 0) {
return;
}
//This result variables are using to store information about subarray sum pairs
var result = 0;
var auxiliary = 0;
for (var i = 0; i < size; ++i) {
auxiliary = collection[i];
for (var j = i + 1; j < size; ++j) {
auxiliary += collection[j];
if (auxiliary == sum) {
result++;
}
}
}
process.stdout.write("Total subarray of sum [" + sum + "] is : " + result + "\n");
}
}
function main(args) {
var obj = new MyArray();
//Define array elements
var collection = [-10, 23, 7, -18, 11, 9, 4, -4, 8, -17];
//Get the size of array
var size = collection.length;
//Test Case
obj.subarray_sum(collection, size, 13);
obj.subarray_sum(collection, size, 9);
}
main();
Output
Total subarray of sum [13] is : 5
Total subarray of sum [9] is : 3# Python 3 Program
# Count subarray with given sum
class MyArray :
# Counting all subarrays of given sum in array
def subarray_sum(self, collection, size, sum) :
if (size <= 0) :
return
result = 0
auxiliary = 0
i = 0
while (i < size) :
auxiliary = collection[i]
j = i + 1
while (j < size) :
auxiliary += collection[j]
if (auxiliary == sum) :
result += 1
j += 1
i += 1
print("Total subarray of sum [", sum ,"] is : ", result ,"\n", end = "")
def main() :
obj = MyArray()
collection = [-10, 23, 7, -18, 11, 9, 4, -4, 8, -17]
size = len(collection)
obj.subarray_sum(collection, size, 13)
obj.subarray_sum(collection, size, 9)
if __name__ == "__main__":
main()
Output
Total subarray of sum [ 13 ] is : 5
Total subarray of sum [ 9 ] is : 3# Ruby Program
# Count subarray with given sum
class MyArray
# Counting all subarrays of given sum in array
def subarray_sum(collection, size, sum)
if (size <= 0)
return
end
result = 0
auxiliary = 0
i = 0
while (i < size)
auxiliary = collection[i]
j = i + 1
while (j < size)
auxiliary += collection[j]
if (auxiliary == sum)
result += 1
end
j += 1
end
i += 1
end
print("Total subarray of sum [", sum ,"] is :", result ,"\n")
end
end
def main()
obj = MyArray.new()
collection = [-10, 23, 7, -18, 11, 9, 4, -4, 8, -17]
size = collection.length
obj.subarray_sum(collection, size, 13)
obj.subarray_sum(collection, size, 9)
end
main()
Output
Total subarray of sum [13] is :5
Total subarray of sum [9] is :3
/*
Scala Program
Count subarray with given sum
*/
class MyArray {
//Counting all subarrays of given sum in array
def subarray_sum(collection: Array[Int], size: Int, sum: Int): Unit = {
if (size <= 0) {
return;
}
var result: Int = 0;
var auxiliary: Long = 0;
var i: Int = 0;
while (i < size) {
auxiliary = collection(i);
var j: Int = i + 1;
while (j < size) {
auxiliary += collection(j);
if (auxiliary == sum) {
result += 1;
}
j += 1;
}
i += 1;
}
print("Total subarray of sum [" + sum + "] is : " + result + "\n");
}
}
object Main {
def main(args: Array[String]): Unit = {
val obj: MyArray = new MyArray();
val collection: Array[Int] = Array(-10, 23, 7, -18, 11, 9, 4, -4, 8, -17);
val size: Int = collection.length;
obj.subarray_sum(collection, size, 13);
obj.subarray_sum(collection, size, 9);
}
}
Output
Total subarray of sum [13] is : 5
Total subarray of sum [9] is : 3/*
Swift Program
Count subarray with given sum
*/
class MyArray {
//Counting all subarrays of given sum in array
func subarray_sum(_ collection: [Int], _ size: Int, _ sum: Int) {
if (size <= 0) {
return;
}
var result: Int = 0;
var auxiliary: Int = 0;
var i: Int = 0;
while (i < size) {
auxiliary = collection[i];
var j: Int = i + 1;
while (j < size) {
auxiliary += collection[j];
if (auxiliary == sum) {
result += 1;
}
j += 1;
}
i += 1;
}
print("Total subarray of sum [", sum ,"] is : ", result ,"\n", terminator: "");
}
}
func main() {
let obj: MyArray = MyArray();
let collection: [Int] = [-10, 23, 7, -18, 11, 9, 4, -4, 8, -17];
let size: Int = collection.count;
obj.subarray_sum(collection, size, 13);
obj.subarray_sum(collection, size, 9);
}
main();
Output
Total subarray of sum [ 13 ] is : 5
Total subarray of sum [ 9 ] is : 3Time Complexity Analysis
Let's analyze the time complexity of the algorithm. The nested loops iterate over the array elements, and for each element, they iterate over the subsequent elements. The number of iterations in the inner loop decreases as we move forward in the array. The worst-case scenario occurs when we have to consider all possible subarrays, leading to a time complexity of O(n^2), where 'n' is the size of the array.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment