# 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

1. Start by initializing the `result` counter to 0.
2. Outer loop iterates over each index 'i' in the array.
3. Initialize an `auxiliary` variable with the value at index 'i'.
4. Inner loop iterates from index 'i+1' to the end of the array.
5. In each iteration of the inner loop, add the current element to the `auxiliary` sum.
6. Check if the `auxiliary` sum is equal to the given `sum`. If it is, increment the `result` counter.
7. 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);

//Test Case
subarray_sum(collection,size,13);
subarray_sum(collection,size,9);
return 0;
}```
```

#### Output

``````Total subarray of sum  is : 5
Total subarray of sum  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);
//Test Case
obj.subarray_sum(collection, size, 13);
obj.subarray_sum(collection, size, 9);
return 0;
}```
```

#### Output

``````Total subarray of sum  is : 5
Total subarray of sum  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  is : 5
Total subarray of sum  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  is : 5
Total subarray of sum  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  is : 5
Total subarray of sum  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  is : 5
Total subarray of sum  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  is  :5
Total subarray of sum  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  is : 5
Total subarray of sum  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 :  3``````

## Time 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.

## Comment

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.