Skip to main content

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[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 :  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.

New Comment