HackerEarth Magic Potion problem solution

In this HackerEarth Magic Potion problem solution, Shruti loves to play with Array. She would always be busy doing some random operation with her array. Today she got to know about Magic Potion. A Magic Potion is a special power that allows you to remove one element from your array either from the start or the end. After spending some time on Magic Potion she decided to use it on her arrays.

Shruti has an array of size N. She calls an array a Good array if the sum of the array is exactly K. She wants to apply Magic Potion on her array so that she could get a good array. She wants to find the count of all the Good arrays that could be formed from the given initial array by applying Magic Potion on them any number of times. She is also interested in finding out the minimum Magic Potion required to form a single Good array. Since she is already quite busy she asks you for help.

HackerEarth Magic Potion problem solution.

#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(false);cin.tie(0);
using namespace std;
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define mp make_pair
#define all(a) a.begin(),a.end()
#define bitcnt(x) __builtin_popcountll(x)
#define mod 1000000007
#define PI 3.14159265
#define tot 300005
#define BLOCK 20000
#define MAXN 500005
typedef unsigned long long int uint64;
typedef long long int int64;

int arr[100005];
int64 k;
int n;
int64 sum[100005];

int64 getsum( int r , int l ){
    return sum[r]-sum[l]+arr[l];
}

int upper(int idx,int l,int r,int64 req){
    if(req<0)
    return -1;
    int lft=l,rht=r;
    int ret=-1;
    while(lft<=rht){
        int mid=(lft+rht);
        mid/=2;
        if(getsum(mid,idx)==req){
            ret=mid;
            lft=mid+1;
        }
        if(getsum(mid,idx)>req)
        rht=mid-1;
        if(getsum(mid,idx)<req)
        lft=mid+1;
    }
    return ret;
}

int lower(int idx,int l,int r,int64 req){
    if(req<0)
    return -1;
    int lft=l,rht=r;
    int ret=-1;
    while(lft<=rht){
        int mid=(lft+rht);
        mid/=2;
        if(getsum(mid,idx)==req){
            ret = mid;
            rht = mid-1;
        }
        if(getsum(mid,idx)>req)
        rht=mid-1;
        if(getsum(mid,idx)<req)
        lft=mid+1;
    }
    return ret;
}

int main(){
    freopen("input.txt","r",stdin);
    freopen("output1.txt","w",stdout);
    cin>>n>>k;
    int cnt=0;
    for(int i=1;i<=n;i++){
        scanf("%d",&arr[i]);
        assert(arr[i]>=0);
        //assert(arr[i]<=10000000000);
        sum[i]=sum[i-1]+arr[i];
        cnt++;
    }
    assert(cnt==n);
    int64 ans=0;
    int minstep = n;
    for(int i=1;i<=n;i++){
        int idx1 = upper(i,i,n,k);
        int idx2 = lower(i,i,n,k);
        if( idx1 != -1 )
            ans+=(idx1-idx2+1);
        minstep = min( minstep , (i-1)+(n-idx1) );
    }
    printf("%lld %d\n",ans,minstep);
    return 0;
}