In this post, we are going to make a c++ program to print the total number of subarrays having a sum exactly equal to k.

## 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 simply print the total number of Subarray sum equals k.

Time complexity for finding number of subarrays sum equals k: O()N^{3}

#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 for C++ program to print total number of sub-arrays having sum exactly equal to k:

Enter 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 10 is 1

Enter array elements:-4 1 3 -2 6 2 -1 -4 -7

Subarray sum equals:10

Total no. of subarray sum equals 10 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 having a sum exactly equal to k. In this program, we are going to make a program that is based on the idea of cumulative sum and this is slightly more optimized than the previous method.

We used three nested loops in the last method and the processor will do a work that is proportional to N3. In this program, we will solve the problem of printing the total number of Subarray sum equals K using two nested loops and the processor will do a work that is proportional to N2.

Time complexity for finding number of subarrays sum equals k using cumulative sum: O()N^{ 2}

#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:

title must be Subarray Sum Equals K leetcode solution :)

ReplyDelete