The Abandoned City - Hackerearth Solution

 

The Abandoned City - C++ Solution

Problem Statement ​

You bought a virtual reality glasses. There is only one game installed to it called "The Abandoned City".

You are lost in an abandoned city. In order to escape, You have to pay a number of golden coins. So, you decided to collect the gold in the houses of that city. The city contains many houses aligned in a straight line. Each house contains a specific amount of golden coins.

You need to figure out the shortest distance you have to walk until you collect the needed amount of golden coins to get out.

Note: You can start from any house i and continue your as $i$ to $i+1$ or $i$ to $i-1$ but you can't change your direction, and stop at any house.

Example

Let's assume that the number of houses is 5 and coins in those houses are $[1,2,3,4,5]$ and target is 7.

It can be seen that to collect 7 coins you will have to travel through atleast 2 houses. The possible travel options are:-

1. Start from $3^{rd}$ house , travel right and stop at $4^{th}$ or start from $4^{th}$ house, travel left and stop at $3^{rd}$ house ,thus collecting 7 coins.
2. Start from $4^{th}$ house , travel right and stop at $5^{th}$ or start from $5^{th}$ house, travel left and stop at $4^{th}$ house ,thus collecting 11 coins.

Thus the shortest distance you have to walk until you collect 7 golden coins is 2.

Function description

Complete the solve function provided in the editor. This function takes the following 3 parameters and returns the minimum distance you have to walk to collect the needed amount of golden coins to get out or -1 if no such answer exists.

• $n$: Represents an integer denoting the number of houses.
• $coins$: Represents an integer array denoting the coins kept in houses. \(coins\) denotes the number of coins kept in $i^{th}$ house.
  [*] $target$ : Represents an integer denoting the target.

Input format

Note: This is the input format that you must use to provide custom input (available above the Compile and Test button).

• The first line contains an integer, $n$, denoting the number of houses.

Output format

Print the minimum distance you have to walk to collect the needed amount of golden coins to get out or -1 if no such answer exists.

C++ Solution

#include<bits/stdc++.h>
using namespace std;

    #define ll long long

    int main(){
        ll n;
        cin>>n;
        ll arr[100005];
        for(ll i=1;i<=n;i++){
            cin>>arr[i];
        }
        ll k;
        cin>>k;
        ll pre[100005];
        pre[0]=0;
        
        for(ll i=1;i<=n;i++){
            pre[i] = pre[i-1]+arr[i];
        }
        if(pre[n]<k){
            cout<<-1<<"\n";
        }
        else{
        ll ans = INT_MAX;
        for(ll i=1;i<=n;i++){
            ll l=i;
            ll r=n;
            ll mid;
            while(l<=r){
                //cout<<l<<" "<<r<<"\n";
                mid = (l+r)/2;
                if(pre[mid]-pre[i-1]>=k){
                    //cout<<mid<<"\n";
                    ans = min(ans,mid-i+1);
                    r=mid-1;
                }
                else
                    l=mid+1;
            }
                    
        }
        cout<<ans<<"\n";
        }
        return 0;
    }

$\mathrm{<br>}$$\mathrm{<br>}$$\mathrm{<br>}$$\mathrm{<br>}$$$\begin{gathered} 1\le n\le {10}^5 \\ 1\le target\le {10}^9 \\ 1\le coin{s}_i\le {10}^5 \end{gathered}$$