4 weeks ago

Sahil Kumar • 260

Gurugram

Q1) Pretty simple House Robber problem on Leetcode.

//Code

using ll=long long int ;
int main() {
   vector <ll> dp(100000,0);
    vector <ll> v={10,15};
    int sz=v.size();
    dp[1]=v[0];
    
    for (int i=2;i<=sz;i++) {
        dp[i]=max(dp[i-2]+v[i-1],dp[i-1]);
    }
    cout<<dp[sz]<<endl;
    return 0;
}

Q2) SImple greedy solution. Solution is independent of values of array. I mean we can sort the array in reverse and try to build answer step by step. Since array is sorted , let say at level x, we have k values then at level x+1, we will have <k values and width constraint is already satisfied. Eg:     at level 3 we have  30,30,30,30 then at level 4 we can atmax have 30,30 ,30 which satisfies the both width and no of boxes constrainsts. I think it is basic math question. I don't see any edges but maybe I am missing something !

//Code starts

using ll=long long int;
int main() {
    
    ll n;
    cin>>n;
    vector <ll> v(n,0);
    for (int i=0;i<n;i++) {
        cin>>v[i];
        
    }
    
    ll cnt=1;
    
    while ( ((cnt)*(cnt+1))<=(2*n)) {
        cnt++;
    }
    
    cout<<(cnt-1)<<endl;
   

    return 0;
}