Category Array

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

UVA 12032 – The Monkey and the Oiled Bamboo

Arunima Mandal Leave a comment

Problem Link: https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3183

Code:

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int t;
    cin>>t;
    for(int z=1; z<=t; z++)
    {
        vector<int> v;
        int n,x,max_distance=-1;
        cin>>n;
        for(int i=0; i<n; i++)
        {
            cin>>x;
            v.push_back(x);
            if(i==0) max_distance=v[0];
            else max_distance=max(max_distance, v[i]-v[i-1]);
        }
        int ans=max_distance;
        for(int i=0; i<n; i++)
        {
            if(i==0)
            {
                if(max_distance==v[0]) max_distance--;
            }
            else if(max_distance==v[i]-v[i-1]) max_distance--;
            else if(max_distance<v[i]-v[i-1])
            {
                ans=ans+1;
                break;
            }
        }
        cout<<"Case "<<z<<": "<<ans<<endl;
    }

    return 0;
}

UVa – 11850 – Alaska

Arunima Mandal Leave a comment

Note:

During solving the problem, I was too confused about two things and faced difficulty due to those. And the realizations are:

  1. Here, it is not mentioned in the problem that whether there is any station in the Delta junction or not. In the solution, it has to be assumed that there is no station in the Delta Junction.
  2. Here, it is stated that the car can travel up to 200 miles once charged, not greater than this limit. So here it is not meant that, at one station, the car takes charge for 200 miles. For how many miles the car is taking charge, it is not mentioned and it is not even the fact. The summary is, the car can travel up to 200 miles at once, not more than that.

Solution:

/*
  Author: Arunima Mandal
*/

#include <bits/stdc++.h>

using namespace std;

bool myfunc(int i,int j)
{
    return (i>j);
}

int main()
{
    int i,j,n,p,q,c,x;
    while(cin>>n)
    {
        if(n==0) break;
        int a[n];
        for(i=0; i<n; i++) cin>>a[i];
        sort(a,a+n);
        c=0;
        for(i=0,j=i+1; i<n-1; i++,j++)
        {

            x=a[j]-a[i];
            if(x>200)
            {
                c=0;
                break;
            }
            if(x<=200) c++;
        }
        if(c==0) cout<<"IMPOSSIBLE"<<endl;
        else
        {
            p=1422-a[n-1];
            q=200-p;
            if(q>=p) cout<<"POSSIBLE"<<endl;
            else cout<<"IMPOSSIBLE"<<endl;
        }
    }
    return 0;
}