Category Uncategorized

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;    
    }

Topological Sorting: Kahn’s algorithm

Arunima Mandal Leave a comment

This algorithm requires no Queue or Stack.

#include <bits/stdc++.h>
#define MAX  2000

using namespace std;

vector<int> topSort(int node, vector<int> &indeg, vector<vector<int> > &adj)
{
    vector<int> ans;
    for(int i=0; i<node; i++) //Inserting all independent nodes first
    {
        if(indeg[i]==0) ans.push_back(i);
    }

    for(int i=0; i<ans.size(); i++)
    {
        int u=ans[i];
        for(int j=0; j<adj[u].size(); j++)
        {
            int v=adj[u][j];
            indeg[v]--;
            if(indeg[v]==0) ans.push_back(v);
        }
    }
    if(ans.size()!=node) ans.clear(); //cycle found, so returning empty vector
    return ans;
}

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);

    int node, edge;
    cout<<"Enter the number of nodes and edges: ";

    while(cin>>node>>edge) //assuming node>=0, edges>=0
    {
        vector<int> indeg(node,0);
        vector<vector<int> > adj(node);
        /* //for string input
        unordered_map<string,int> mp;
        unordered_map<int,string> mp;
        int c=0;
        */

        if(edge==0) //Print all nodes as all are independent
        {
            for(int i=0; i<node; i++) cout<<i<<" ";
            cout<<endl;
        }

        cout<<"Enter the relations(pair of edges): "<<endl;

        for(int i=0; i<edge; i++) //Populating Adjacency list and indeg array for TopSort
        {
            int from,to;
            //string from,to;
            cin>>from>>to;

            /* //Processing string input

            if(mp1[from]==0)
            {
                mp1[from]=++c;
                mp2[c]=from;
            }
            if(mp1[to]==0)
            {
                mp1[to]=++c;
                mp2[c]=to;
            }
            g[mp1[from]].pb(mp1[to]);
            indeg[mp1[to]]++;
            */
            adj[from].push_back(to);
            indeg[to]++;
        }

        vector<int> ans=topSort(node, indeg, adj);

        if(ans.size()>0) //Ordering possible
        {
            cout<<"The correct ordering is:";
            for(int i=0; i<ans.size(); i++)
            {
                cout<<" "<<ans[i];
                //cout<<mp2[ans[i]]<<" ";
            }
            cout<<endl;
        }
        else cout<<"Cycle exists"<<endl; //Ordering not possible
    }
    return 0;
}

Iterative DFS for Detecting Cycle in any Directed Graph

Arunima Mandal Leave a comment

Note:

The algorithm for detecting cycles in any directed graph is easier using recursive DFS. But Iterative DFS approach to detect a cycle is a bit complex and tricky. I have commented on the code where necessary to make the algorithm more understandable.

In any case, the time complexity of the algorithm is O(V+E). 

#include <bits/stdc++.h>

using namespace std;

#define MAX 100005

bool detectCycle(int nodes, vector<vector<int> >& adjList)
{
    if(nodes==1) return false;
    stack<int> st;
    bool on_stack[MAX+1]= {0};
    bool visited[MAX+1]= {0};
    for(int i=0; i<nodes; i++) //In case the graph is disconnected
    {
        if(visited[i]) continue; //For time efficiency
        st.push(i);
        while(!st.empty())
        {
            int u=st.top();
            if(!visited[u])
            {
                visited[u]=1;
                on_stack[u]=1;
            }
            else //backtracking, but keeping the visited array unchanged for time efficiency
            {
                on_stack[u]=0;
                st.pop();
                continue;
            }
            for(int j=0; j<adjList[u].size(); j++)
            {
                int v=adjList[u][j];
                if(!visited[v])
                {
                    st.push(v);
                }
                else
                {
                    if(on_stack[v]) return true; //cycle detected
                }
            }
        }
    }
    return false;
}


int main()
{
    vector<vector<int> > adjList(MAX+1);
    int nodes, edges;
    cout<<"Enter the number of nodes: ";
    cin>>nodes;
    cout<<endl;
    cout<<"Enter the number of edges: ";
    cin>>edges;
    cout<<endl;
    cout<<"Enter the pair of edges: "<<endl;
    for(int i=0; i<edges; i++)
    {
        int from, to;
        cin>> from>> to;
        adjList[from].push_back(to);
    }
    if(detectCycle(nodes, adjList)==1) cout<<"Cycle found!"<<endl;
    else cout<<"Cycle not found!"<<endl;
    return 0;
}

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 – 673 – Parentheses Balance

Arunima Mandal Leave a comment

Problem Link: https://onlinejudge.org/external/6/673.pdf

Note:
This can be solved using different data structures and logic. I have used Stack to approach the problem.

Solution:

/*
Author: Arunima Mandal
Updated Date: 06.16.2020
*/
#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 db double
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<long,long>
#define ff first
#define ss second
#define sz(x) (int)x.size()
#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 for0(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define forrev(i,n) for(int i=n-1; i>=0; i--)
#define forab(i,a,b) for(int i=a;i<=b;i++)
#define forba(i,b,a) for(int i=b;i>=a;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 acos(-1) //3.14159265358979323846264338328
#define valid(tx,ty) tx>=0 && tx<row && ty>=0 && ty<col
#define intlim 2147483648
#define MAX 1000006
#define inf 100000008
ll power(int n,int p)
{
ll ans=1;
for1(i,p) ans*=n;
return ans;
}
ll m=1000001;
ll bigmod(ll n,ll p)
{
if(p==0) return 1;
else if(p%2==0)
{
ll x=(bigmod(n,p/2))%m;
return (x*x)%m;
}
else return ((n%m)*(bigmod(n,p-1)%m))%m;
}
/*------------------------------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;
stack<char> st;
string s;
int main()
{
// CIN; //if getline() is present, it can't be used.
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int t,d;
sf(t);
getchar();
for0(z,t)
{
getline(cin,s);
d=0;
for0(i,sz(s))
{
if(s[i]=='(' || s[i]=='{' || s[i]=='[')
{
st.push(s[i]);
}
else if(s[i]==' ') continue;
else
{
if(!st.empty())
{
char ch=st.top();
if((ch=='(' && s[i]==')') || (ch=='{' && s[i]=='}') || (ch=='[' && s[i]==']'))
{
st.pop();
}
else break;
}
else {d=1; break;} //there is nothing left in stack to compare with.
}
}
if(!d && st.empty()) pf("Yes\n");
else
{
pf("No\n");
while(!st.empty()) st.pop();
}
}
return 0;
}
view raw UVA 673 - Parentheses Balance.cpp hosted with ❤ by GitHub