De Shaw OA | SDE | Set - 55 | Kumar K

Question

Answer 1

#include <bits/stdc++.h>
//
using namespace std;
typedef long long int ll ;
vector <ll> b ;
ll n,k ;
bool check(ll g){
    
    //sz =====> k
    //=====> g
    ll t = g*k ;
    
    ll i = 1 ;
    while(i<=n){
        
        if(b[i]>g){
            t = t - g ;
        } else {
            t = t - b[i] ;
        }
        
        i++;
    }
    
    if(t<=0){
        return true ;
    }
    
    
    
    return false ;
    
}

int main() {
    
    
    
    cin>>n;
    cin>>k;
    b.resize(n+5,0);
    
    ll sum = 0 ;
    ll i = 1 ;
    while(i<=n){
        cin>>b[i] ;
        sum = sum + b[i] ;
        i++;
    }
    //cout<<sum ;
    //cout<<"\n";
    
    ll ans = 0 ;
    
    /*
    ll g = 1 ;
    while(g<=sum){
        
        if(check(g)==true){
            ans = g ;
        } else {
            g = 1e18 ;
        }
        
        g++;
    }
    */
    
    
    ll low = 1 ;
    ll high = 1e18 ;
    ll y = 0 ;
    
    while(low<=high && y==0){
        
        ll mid = (low+high)/2 ;
        
        if(check(mid)==true && check(mid+1)==false){
            ans = mid ;
            y = 1 ;
        }
        else if(check(mid)==true){
            low = mid ; //right....................
        } else {
            
            high = mid - 1 ; //left......
        }
        
        
        
        
    }
    
    
    
    
    
    
    
    cout<<ans ;
    
    return 0 ;
}

Answer 2

Example -

/*
4 2
2 3 5 3

Output  6

*/

Answer 3

Image of the question : 

Comments

can anyone please solve this question

---

did it ................