In this post, we will make a C++ program to print the total number of subarray sums equals k. We will also code another program based on the idea of a cumulative sum.

## Total Number of Subarrays whose Sum Equals k

Given an unsorted array of integers. We will find the number of continuous subarrays having a sum exactly equal to k in linear time complexity. We will use hashmap to store prefix sum.

`int subarraySum(vector<int>& nums, int k) {        int sum=0,ans=0;        unordered_map<int,int> mp;        mp = 1; // we always have 1 sum of zero, which is sum of none.        for(int i=0;i<nums.size();i++)        {            sum+=nums[i];                    // We have x prefix array to create this value. So count is added with the existing combinations            if(mp.find(sum-k)!=mp.end())                ans+=mp[sum-k];            mp[sum]++;        }        return ans;    }`

## C++ Program to Print Total Number of Subarrays having Sum Exactly Equal to K

In this program, we will make a program that takes an array from the user and Subarray sum(k). We will print the total number of Subarray sums equal to k.

Time complexity for finding the number of subarrays sum equals k: O( N3)

`#include<iostream>using namespace std;int main(){    int arr, k, n, ksum, currentsum, count = 0;    cout<<"n Enter number of elements:";    cin>>n;    cout<<"n Enter array elements:";    for (int i = 0; i < n; i++)    {        cin>>arr[i];    }    cout<<"n Subarray sum equals:";    cin>>ksum;    for (int i=0; i<n; i++)    {        for(int j = i; j < n; j++)        {            currentsum=0;            for(int k = i; k <= j; k++)            {                currentsum+= arr[k];            }            if ( currentsum == ksum)            count++;        }    }    cout<<"Total no. of subarray sum equals "<<ksum<<" is ";    cout<<count;    return 0;    }    `
Output:

Enter the number of elements:9
Enter array elements:-4 1 3 -2 6 2 -1 -4 -7
Subarray sum equals:10
Total no. of subarray sum equals ten is 1

## Program to Print Total number of Subarray Sum equals k using Cumulative Sum

In the last program, we made a program to print the total number of subarrays with a sum equal to k. In this program, we will make a program based on the idea of cumulative sum, which is slightly more optimized than the previous method.
We used three nested loops in the last method, and the processor will do work that is proportional to N 3. In this program, we will solve the problem of printing the total number of Subarray sums equals K using two nested loops, and the processor will do work proportional to N 2.

The time complexity for finding the count of subarrays sum equals k using cumulative sum: O( N 2)

`#include<iostream>using namespace std;int main(){    int arr, k, n, ksum, currentsum, count = 0,cumulativesum={0};    cout<<"n Enter number of elements:";    cin>>n;    cout<<"n Enter array elements:";    cin>>arr;    cumulativesum=arr;    for (int i = 1; i < n; i++)      {        cin>>arr[i];        cumulativesum[i] = cumulativesum[i-1] + arr[i];    }    cout<<"n Subarray sum equals:";    cin>>ksum;    for (int i=0; i<n; i++)    {        for(int j = i; j < n; j++)        {            currentsum=0;            currentsum = cumulativesum[j] - cumulativesum[i-1];            if ( currentsum == ksum)            count++;        }               }    cout<<"Total no. of subarray sum equals "<<ksum<<" is ";    cout<<count;    return 0;    }    `

Related posts: