Category Cummulative Sum

Number of subarrays having a sum exactly equal to k

Arunima Mandal Leave a comment

Note:

This problem states that – Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals k.

Brute force method: It comes to the mind easily. Time complexity is O(n^2) and space complexity is O(1). So in most cases, this solution would exceed the time limit.

int subarraySum(vector<int>& nums, int k) {
        int ans=0;
        for(int i=0; i<nums.size(); i++)
        {
            int total=0;
            for(int j=i; j<nums.size(); j++)
            {
                total+=nums[j];
                if(total==k) ans++;
            }
        }
        return ans;    
    }

Cumulative /Prefix Sum:

Though this thing doesn’t come to mind at first, this way is the more efficient one. The main trick is we have to keep the cumulative sum in an array first, then we’ll have to work on that array. The first idea is that to know the sum of any subarray in the range [i,j], the equation would be: sum=a[j]-a[i-1] (assuming a is the cumulative sum array). Since our sum has to be k, so we can write, k=a[j]-a[i-1]. Alternatively, we can write, a[i-1]=a[j]-k. Now we will have to run a loop for each j, to see whether there is any prefix sum equal to a[i-1] till now. We’ll check that with the help of a hashmap. If our condition is satisfied, we increase our answer variable by the count in the hashmap.

Time complexity: O(N)
Space complexity: O(N); for the hashmap.

int subarraySum(vector<int>& nums, int k) {
        unordered_map<int,int> ump;
        ump[0]=1;
        int a[20004]={0};
        int ans=0;
        for(int i=0; i<nums.size(); i++)
        {
            if(i==0) a[i]=nums[i];
            else a[i]=a[i-1]+nums[i];
            
            int x=a[i]-k;
            if(ump.count(x)) ans+=ump[x];
            ump[a[i]]++;
        }
        return ans;    
    }

Codeforces Round #797 (Div. 3) – D. Black and White Stripe

Arunima Mandal Leave a comment

Problem Link:
https://codeforces.com/contest/1690/problem/D
Note: This is quite an interesting problem for cumulative sum or prefix sum.
Solution

#include <bits/stdc++.h>

using namespace std;

int a[200005];
queue<int> q;
int main ()
{
    int t;
    cin>>t;
    int n,k;
    string s;

    for(int z=0;z<t; z++)
    {
        cin>>n>>k;
        cin>>s;
        bool d=0;
        for(int i=1;i<=n;i++)
        {
            if(s[i-1]=='W') a[i]=a[i-1]+1;
            else a[i]=a[i-1];
        }
        int mini=20000005;
        for(int i=k;i<=n;i++)
        {
            mini=min(mini,a[i]-a[i-k]);
        }
        cout<<mini<<endl;
    }

    return 0;
}

UVa – 10324 – Zeroes and Ones

Arunima Mandal Leave a comment 

#include <bits/stdc++.h>

#define pf                  printf
#define sf(a)               scanf("%d",&a)
#define sfl(a)              scanf("%lld",&a)
#define sff(a,b)            scanf("%d %d",&a,&b)
#define sffl(a,b)           scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)         scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)        scanf("%lld %lld %lld",&a,&b,&c)
#define sffff(a,b,c,d)      scanf("%d %d %d %d",&a,&b,&c,&d)
#define sffffl(a,b,c,d)     scanf("%lld %lld %lld %lld",&a,&b,&c,&d)
#define sfffff(a,b,c,d,e)   scanf("%d %d %d %d %d",&a,&b,&c,&d,&e)
#define sfffffl(a,b,c,d,e)  scanf("%lld %lld %lld %lld %lld",&a,&b,&c,&d,&e)
#define sfc(a)              scanf("%c",&a)
#define ms(a,b)             memset(a,b,sizeof(a))
#define pb(a)               push_back(a)
#define pbp(a,b)            push_back({a,b})
#define db                  double
#define ft                  float
#define ll                  long long
#define ull                 unsigned long long
#define ff                  first
#define ss                  second
#define sz(x)               x.size()
#define qu                  queue
#define pqu                 priority_queue
#define vc                  vector
#define vi                  vector<int>
#define vll                 vector<long long>
#define pii                 pair<int,int>
#define pis                 pair<int,string>
#define psi                 pair<string,int>
#define all(x)              x.begin(),x.end()
#define CIN                 ios_base::sync_with_stdio(0); cin.tie(0)
#define max3(a, b, c)       max(a, b) > max(b, c) ? max(a, b) : max(b, c)
#define min3(a, b, c)       min(a, b) < min(b, c) ? min(a, b) : min(b, c)
#define loop0(i,n)          for(int i=0;i<n;i++)
#define loopn(i,n)          for(int i=1;i<n;i++)
#define loop1(i,n)          for(int i=1;i<=n;i++)
#define loopab(i,a,b)       for(int i=a;i<=b;i++)
#define loopba(i,b,a)       for(int i=b;i>=a;i--)
#define REV(i,n)            for(i=n; i>=0; i--)
#define stlloop(x)          for(__typeof(x.begin()) it=x.begin();it!=x.end();it++)
#define gcd(a, b)           __gcd(a, b)
#define lcm(a, b)           ((a)*((b)/gcd(a,b)))
#define case1(z)            cout<<"Case "<<z<<": "
#define case2(z)            printf("Case %d: ",z)
#define PI                  3.14159265358979323846264338328
#define valid(tx,ty)        tx>=0 && tx<r && ty>=0 && ty<c
#define intlim              2147483648
#define MAX                 1000000
#define inf                 10000000

/*------------------------------Graph Moves----------------------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*---------------------------------------------------------------------*/

using namespace std;

int a[1000005];

int main()
{
    CIN;
    int n,i,j,k,l,c,m=1;
    string s;
    while(cin>>s)
    {
        if(s=="\n") break;
        for(i=0; i<s.size(); i++)
        {
            if(s[i]=='1') a[i+1]=1;
            else a[i+1]=0;
        }
        for(i=1; i<=s.size(); i++) a[i]+=a[i-1];
        cin>>n;
        cout<<"Case "<<m<<":"<<endl;
        for(l=0; l<n; l++)
        {
            cin>>i>>j;
            c=0;
            i++,j++;
            if(i>j) swap(i,j);

            if(a[j]-a[i-1]==0 || a[j]-a[i-1]==(j-i+1))
                cout<<"Yes"<<endl;
            else
                cout<<"No"<<endl;
        }
        m++;
    }
    return 0;
}

UVa – 12527 – Different Digits

Arunima Mandal Leave a comment

Thsi problem can be solved in the “Brute Force” way like this ->

#include <bits/stdc++.h>

using namespace std;

int b[15],a[10000];
int n,m,c,i,j,k,p,x,y;

int main()
{
    while(cin>>n>>m)
    {
        x=((m-n)+1);
        c=0;
        for(i=n; i<=m; i++)
        {
            memset(b,0,sizeof(b));
            j=0;
            p=i;
            while(p!=0)
            {
                a[j]=p%10;
                p=p/10;
                j++;
            }
            for(k=0; k<j; k++)
            {
                b[a[k]]++;
                if(b[a[k]]>1)
                {
                    c++;
                    break;
                }
            }
        }
        y=x-c;
        cout<<y<<endl;
    }
    return 0;
}

But the following code can be done using “Cummulative Sum” which is more efficient,better and the fastest way in terms of complexity !! Coz Cummulative sum is just a disguess of DP !! 😀 Which prohibits us to calculate the same thing repeatedly and thus minimizing time complexity 🙂


#include <bits/stdc++.h>

#define pf                  printf
#define sf(a)               scanf("%d",&a)
#define sfl(a)              scanf("%lld",&a)
#define sff(a,b)            scanf("%d %d",&a,&b)
#define sffl(a,b)           scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)         scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)        scanf("%lld %lld %lld",&a,&b,&c)
#define sffff(a,b,c,d)      scanf("%d %d %d %d",&a,&b,&c,&d)
#define sffffl(a,b,c,d)     scanf("%lld %lld %lld %lld",&a,&b,&c,&d)
#define sfffff(a,b,c,d,e)   scanf("%d %d %d %d %d",&a,&b,&c,&d,&e)
#define sfffffl(a,b,c,d,e)  scanf("%lld %lld %lld %lld %lld",&a,&b,&c,&d,&e)
#define sfc(a)              scanf("%c",&a)
#define ms(a,b)             memset(a,b,sizeof(a))
#define pb(a)               push_back(a)
#define pbp(a,b)            push_back({a,b})
#define db                  double
#define ft                  float
#define ll                  long long
#define ull                 unsigned long long
#define ff                  first
#define ss                  second
#define sz(x)               x.size()
#define qu                  queue
#define pqu                 priority_queue
#define vc                  vector
#define vi                  vector<int>
#define vll                 vector<long long>
#define pii                 pair<int,int>
#define pis                 pair<int,string>
#define psi                 pair<string,int>
#define all(x)              x.begin(),x.end()
#define CIN                 ios_base::sync_with_stdio(0); cin.tie(0)
#define max3(a, b, c)       max(a, b) > max(b, c) ? max(a, b) : max(b, c)
#define min3(a, b, c)       min(a, b) < min(b, c) ? min(a, b) : min(b, c)
#define loop0(i,n)          for(int i=0;i<n;i++)
#define loopn(i,n)          for(int i=1;i<n;i++)
#define loop1(i,n)          for(int i=1;i<=n;i++)
#define loopab(i,a,b)       for(int i=a;i<=b;i++)
#define loopba(i,b,a)       for(int i=b;i>=a;i--)
#define REV(i,n)            for(i=n; i>=0; i--)
#define stlloop(x)          for(__typeof(x.begin()) it=x.begin();it!=x.end();it++)
#define gcd(a, b)           __gcd(a, b)
#define lcm(a, b)           ((a)*((b)/gcd(a,b)))
#define case1(z)            cout<<"Case "<<z<<": "
#define case2(z)            printf("Case %d: ",z)
#define PI                  3.14159265358979323846264338328
#define valid(tx,ty)        tx>=0 && tx<r && ty>=0 && ty<c
#define intlim              2147483648
#define MAX                 1000000
#define inf                 10000000

/*------------------------------Graph Moves----------------------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*---------------------------------------------------------------------*/

using namespace std;

int ara[5005];
bool visit[11];

int main()
{
    for(int i=1; i<=5003; i++)
    {
        int a=i;
        ms(visit,0);
        bool test=0;
        while(a)
        {
            int x=a%10;
            a/=10;
            if(visit[x]==0)
                visit[x]=1;
            else
            {
                test=1;
                break;
            }
        }
        if(test==0) ara[i]++;
    }
    for(int i=1; i<5003; i++) ara[i]+=ara[i-1];
    int a,b;
    while(cin>>a>>b) cout<<ara[b]-ara[a-1]<<endl;
    return 0;
}