Help me in solving WARRIORCHEF problem

help
,
1

My issue

How to solve this ques using Binary search???
I know this is wrong code but please rectify and tell the correct soln?

My code

#include <bits/stdc++.h>
using namespace std;
int check(a,n,mid){
    bool flg=false;
    int left=h;
    for(int i=0;i<n;i++){
        if(a[i]<=mid){
            flg=true;
            ans=mid;
        }
        else{
            left=left-a[i];
            if(left<0){
                break;
            }
        }
    }
    return mid;
}
int main() {
	// your code goes here
	int t;cin>>t;
	while(t--){
	    int n,h;cin>>n>>h;
	    vector<int> a(n);
	    for(int i=0;i<n;i++){
	        cin>>a[i];
	    }
	    int low=0,high=*max_element(a.begin(),a.end());
	    while(low<=high){
	        int mid=(low+high)/2;
	        if(check(a,n,mid)>0){
                high=mid-1;
	        }
	        else{
	            low=mid+1;
	        }
	    }
	}

}

Problem Link: Warrior Chef Practice Coding Problem

2

Made some changes in your code

#include <bits/stdc++.h>
#include<iostream>
using namespace std;
bool check(vector<int> a,int h,int mid){
    bool flg=false;
    int left=h;
    for(int i=0;i<a.size();i++){
        if(a[i]<=mid){
            flg=true;
        }
        else{
            left=left-a[i];
            if(left<0){
                break;
            }
        }
    }
    return left>0;
}
int main() {
	// your code goes here
	int t;cin>>t;
	while(t--){
	    int n,h;
	    cin>>n>>h;
	    vector<int> a(n);
	    for(int i=0;i<n;i++){
	        cin>>a[i];
	    }
	    int low=0,high=*max_element(a.begin(),a.end());
	    int ans=high;
	    while(low<=high){
	        int mid=(low+high)/2;
	        if(check(a,h,mid)){
	            ans=mid;
                high=mid-1;
	        }
	        else{
	            low=mid+1;
	        }
	    }
	    cout<<ans<<endl;
	}

}
1 Like