Google | OA | Online Coding Test Questions and Solutions | Set - 30 | 2022

Question

Answer 1

Constraints :

1<=n<=100000

1<=a[i]<=100000000

Answer 2

#include <bits/stdc++.h>

using namespace std;
typedef long long int ll ; 
vector <ll> b ; 
ll n ; 
bool check(ll vl){
    vector <ll> gg = b ; 
    ll i = n ; 
    while(i>=2){
        
        if(b[i]>=vl){
            ll gg = abs(b[i]-vl);
            b[i-1]+=gg ; 
        }
        
        
        i--;
    }
    
    if(b[1]<=vl){
        b = gg  ;
        return true ; 
    }
    b = gg ; 
    return false ; 
}

int main() {
    b.clear();
    cin>>n ; 
    b.resize(n+5,0);
    ll i = 1 ;
    ll vv = 0 ; 
    while(i<=n){
        cin>>b[i];
        vv = max(vv,b[i]);
        //cout<<b[i]<<"\n";
        i++;
    }
    
    i = 0 ; ll rr = 1e18 ; 
    while(i<=vv){
        
        if(check(i)==true){
            rr = i ; 
            break ; 
        } else {
            
        }
        
        
        i++;
    }
    cout<<rr ; 
    
    return 0 ; 
}
//TC - O(N*max) 

Answer 3

#include <bits/stdc++.h>
//RR.....
using namespace std;
typedef long long int ll ; 
vector <ll> b ; 
ll n ; 
bool check(ll vl){
    vector <ll> gg = b ; 
    ll i = n ; 
    while(i>=2){
        
        if(b[i]>=vl){
            ll gg = abs(b[i]-vl);
            b[i-1]+=gg ; 
        }
        
        
        i--;
    }
    
    if(b[1]<=vl){
        b = gg  ;
        return true ; 
    }
    b = gg ; 
    return false ; 
}
//TC : O(N*LogN) 
//TC : O(N*log(max(a[i]))) 
int main() {
    b.clear();
    cin>>n ; 
    b.resize(n+5,0);
    ll i = 1 ;
    ll vv = 0 ; 
    while(i<=n){
        cin>>b[i];
        vv = max(vv,b[i]);
        //cout<<b[i]<<"\n";
        i++;
    }
    //0......vv vv = maximum array element 
    ll low = 0 ; 
    ll k = 1 ; 
    ll high = vv ; ll rr = 1e18  ; 
    while(low<=high && k==1){
        
        ll md = (low+high)/2 ;
        
        if(md==0){
            rr = md ; 
            k = 0 ; 
        }
        
        if(check(md)==true && check(md-1)==false){
            rr = md ;
            k = 0 ; 
        } else if(check(md)==true){
            high = md ; 
        } else {
            low = md + 1 ; 
        }
    }
    cout<<rr ; 
    
    return 0 ; 
}

Answer 4

Image of the problem :