Array-Sum operations(Hack the interview Hackerrank)

general
, ,
1

Problem
My code fails for 4 test cases. Can anyone point out the mistake?

Code 
#include<bits/stdc++.h>
#define lli long long int
#define fio ios_base::sync_with_stdio(false); cin.tie(NULL);
#define pb push_back
#define endl "\n"
using namespace std; 
lli binarySearch(vector<lli>&arr,lli l,lli r,lli x) 
{ 
    if (r >= l) { 
        lli mid = l + (r - l) / 2; 
        if (arr[mid] == x) 
            return mid; 
  
       
        if (arr[mid] > x) 
            return binarySearch(arr, l, mid - 1, x); 
  
        return binarySearch(arr, mid + 1, r, x); 
    } 
    return -1; 
} 
int main(){
     fio;
     lli n,m;
     cin>>n>>m;
     vector<lli>v;
     lli sum=(n*(n+1))/2;
     for(int i=0;i<n;i++){
         v.pb(i+1);
     }
     while(m--){
        lli z;
        cin>>z;
        if(binarySearch(v,0,v.size()-1,z)!=-1){
            cout<<sum<<endl;
            vector<lli>::iterator i1, i2; 
            i1 = v.begin(); 
            i2 = v.end()-1;  
            iter_swap(i1, i2); 
        }
        else{
            lli x=v.back();
            v.back()=z;
            cout<<sum-x+v.back()<<endl;
            lli value=sum-x+v.back();
            sum=value;
        }
     }
}
2

instead of bin search, try to check if it’s in range 2,n-1(also seprately for 1st n last). (2 to n-1) elemnts will not change only 1st n last index change

1 Like
3

I get it, and thats another way. But whats the wrong with the bsearch as it does the same?

4

A binary search requires that arr be in sorted order, which it won’t always be.

Edit: Your code doesn’t compile, btw

Edit2:

For a specific test input for which your solution fails, consider:

3 3
4
2
4
2 Likes
5

Forgot this simple thing. Thanks @ssjgz and @chef_ka_baap.

1 Like
6

Yes, my code is now accepted. Just changed the binary search if statement to

if((z>=2 and z<=n-1) or (z==v[0] or z==v.back())

Thank you

1 Like