Subarray Sum Equals K in Linear Time Complexity [New]

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

Table of Contents

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 a given number k in linear time complexity. We will use hashmap to store prefix sum.

Problem link: Leetcode

int subarraySum(vector<int>& nums, int k) {
        int sum=0,ans=0;
        unordered_map<int,int> mp;
        mp[0] = 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( N³)

#include<iostream>
using namespace std;
int main()
{
    int arr[1000], 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

Video Solution

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 ³. 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 ².

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

#include<iostream>
using namespace std;
int main()
{
    int arr[1000], k, n, ksum, currentsum, count = 0,cumulativesum[1000]={0};
    cout<<"\n Enter number of elements:";
    cin>>n;
    cout<<"\n Enter array elements:";
    cin>>arr[0];
    cumulativesum[0]=arr[0];
    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:

Menu Driven Program for Singly Linked List in C++ 

Menu-Driven Program for Array Operations in C++

Binary Tree traversal in C++

About this post:

Siddharth Jha writes this post. In this post, we print the total number of subarrays having a sum equal to k using three nested. In another program, we used the concept of cumulative sum and showed the number of subarray sums equal to k using two nested loops.