Number of Subarrays having Sum Exactly Equal to K

1 comment

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.


    Number of Subarrays having 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( N3)


    #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

    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:

    About this post:

    This post is written by Siddharth Jha. In this post, we print the total number of subarrays having a sum exactly equal to k using three nested. In another program, we used the concept of cumulative sum and printed the number of subarray sum equals k using two nested loops.

    Siddharth Jha
    • Hackerrank 5* • Full Stack Developer • Masters in SEO

    Related Posts

    1 comment

    1. title must be Subarray Sum Equals K leetcode solution :)

      ReplyDelete

    Post a Comment

    Follow by Email