HackerEarth New World problem solution

In this HackerEarth New World problem solution, The time has arrived when the world is going to end. But don’t worry, because the new world yuga will start soon. Manu (carrier of mankind) has been assigned the job to carry all the necessary elements of the current yuga to the upcoming yuga.

There are N stones arranged in a straight line. In order to fulfill the task, Manu has to travel from the first stone to the last one in a very specific way. First of all, he has to do it using exactly K jumps. In a single jump, he can jump from a stone with coordinate xi to a stone with coordinate xj if and only if xi < xj. We denote the value xj – xi as the length of such a jump.

Your task is to help Manu minimize the maximum length of a jump he makes in his journey, in order to reach the last stone in exactly K jumps and save mankind. This is the answer you have to provide.

HackerEarth New World problem solution.

#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(false);cin.tie(0);
using namespace std;
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define mp make_pair
#define all(a) a.begin(),a.end()
#define bitcnt(x) __builtin_popcountll(x)
#define MOD 1000000007
#define BASE 31
typedef unsigned long long int uint64;
typedef long long int int64;
 
int stone[100005];

bool chck(int dist,int n,int k){
    int req=0,cur=0,pre=0;
    
    for(int i=0;i<n;i++){
        while((cur!=n)&&(stone[cur]-stone[pre]<=dist))
        cur++;
        req++;
        if(cur==n)
        break;
        pre=cur-1;
    }
    if(cur!=n)
    return false;
    if(req<=k)
    return true;
    return false;
}

int main(){
    int t,n,k,i;
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    cin>>t;
    while(t--){
        cin>>n>>k;
        for(i=0;i<n;i++)
        cin>>stone[i];
        
        int lo=1,hgh=1e9,ans=-1;
        
        while(lo<=hgh){
            int mid=(lo+hgh);
            mid/=2;
            if(chck(mid,n,k)){
                ans=mid;
                hgh=mid-1;
            }
            else{
                lo=mid+1;
            }
        }
        cout<<ans<<endl;
    }
    fclose(stdout);
    return 0;
}

coding problems solutions