HackerRank Travel around the world Solution

In this post, we will solve HackerRank Travel around the world Problem Solution.

There are N cities and N directed roads in Steven’s world. The cities are numbered from 0 to N – 1. Steven can travel from city i to city (i + 1) % N, ( 0-> 1 -> 2 -> …. -> N – 1 -> 0).

Steven wants to travel around the world by car. The capacity of his car’s fuel tank is C gallons. There are a[i] gallons he can use at the beginning of city i and the car takes b[i] gallons to travel from city i to (i + 1) % N.

How many cities can Steven start his car from so that he can travel around the world and reach the same city he started?

Note

The fuel tank is initially empty.

Input Format

The first line contains two integers (separated by a space): city number N and capacity C.
The second line contains N space-separated integers: a[0], a[1], … , a[N – 1].
The third line contains N space-separated integers: b[0], b[1], … , b[N – 1].

Constraints

2 ≤ N ≤ 10⁵
1 ≤ C ≤ 10¹⁸
0 ≤ a[i], b[i] ≤ 10⁹

Output Format

The number of cities which can be chosen as the start city.

Sample Input

3 3
3 1 2
2 2 2

Sample Output

Explanation

Steven starts from city 0, fills his car with 3 gallons of fuel, and use 2 gallons of fuel to travel to city 1. His fuel tank now has 1 gallon of fuel.
On refueling 1 gallon of fuel at city 1, he then travels to city 2 by using 2 gallons of fuel. His fuel tank is now empty.
On refueling 2 gallon of fuel at city 2, he then travels back to city 0 by using 2 gallons of fuel.

Here is the second possible solution.
Steven starts from city 2, fill his car with 2 gallons, and travels to city 0.
On refueling 3 gallons of fuel from city 0, he then travels to city 1, and exhausts 2 gallons of fuel. His fuel tank contains 1 gallon of fuel now. He can then refuel 1 gallon of fuel at City 1, and increase his car’s fuel to 2 gallons and travel to city 2.

However, Steven cannot start from city 1, because he is given only 1 gallon of fuel, but travelling to city 2 requires 2 gallons.

Hence the answer 2.

HackerRank Travel around the world Problem Solution

Travel around the world C Solution


#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main() {
    int N,i,flag=0;
    long long C,*dp;
    int *a,*b,ans=0;
    scanf("%d%lld",&N,&C);
    a=(int*)malloc(N*sizeof(int));
    b=(int*)malloc(N*sizeof(int));
    dp=(long long*)malloc(2*N*sizeof(long long));
    for(i=0;i<N;i++)
        scanf("%d",a+i);
    for(i=0;i<N;i++)
        scanf("%d",b+i);
    for(i=0;i<2*N;i++)
        dp[i]=1;
    for(i=0;i<N;i++){
if(!i)
dp[i]=0;
else if(a[N-1-i]<=C)
dp[i]=dp[i-1]-a[N-1-i]+b[N-1-i];
    else
    dp[i]=dp[i-1]-C+b[N-1-i];
        if(dp[i]<0)dp[i]=0;
if(dp[i]+((a[N-1-i]>C)?C:a[N-1-i])>C){
flag=1;
    //printf("break at %d\n",i);
break;
}
}
if(!flag){
for(i=0;i<N;i++){
    if(a[N-1-i]<=C)
dp[i+N]=dp[i-1+N]-a[N-1-i]+b[N-1-i];
    else dp[i+N]=dp[i-1+N]-C+b[N-1-i];
    if(dp[i+N]<0)dp[i+N]=0;
if(dp[i+N]+((a[N-1-i]>C)?C:a[N-1-i])>C){
dp[i+N]=1;//printf("break at %d\n",i);
break;
}
}

}

    //for(i=0;i<2*N;i++)
        //printf("%lld ",dp[i]);
    //printf("\n");
    
    for(i=0;i<N;i++)
        if(dp[i+N]<=0)
        ans++;
        printf("%d",ans);
    return 0;
}

Travel around the world C++ Solution

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

int main() {
    ll n,j,ans=0,i;
    ll d,diff=0;
    cin>>n>>d;
    vector<ll> a(n*2),b(n*2);
    for(i=0;i<n;i++)
    {
        cin>>a[i];
        a[i]=min(d,a[i]);
        a[i+n]=a[i];
    }
    for(i=0;i<n;i++)
    {
        cin>>b[i];
        b[i+n]=b[i];
    }
    bool invalid[n]={false};
    for(i=((2*n)-1);i>=n;i--)
    {
        if(invalid[i%n])
            continue;
        if(b[i]>d)
        {
            cout<<"0";
            return 0;
        }
        if(b[i]>a[i])
        {
            invalid[i%n]=true;
            diff=b[i]-a[i];
            j=i-1;
            while(j>=0&&diff>0)
            {
                diff+=b[j];
                if(diff>d)
                {
                    cout<<"0";
                    return 0;
                }
                diff-=a[j];
                if(diff>0)
                    invalid[j%n]=true;
                j--;
            }
        }
    }
    for(i=0;i<n;i++)
        ans+=invalid[i]?0:1;
    cout<<ans;
    return 0;
}

Travel around the world C Sharp Solution

using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;

class Result
{

    /*
     * Complete the 'travelAroundTheWorld' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts following parameters:
     *  1. INTEGER_ARRAY a
     *  2. INTEGER_ARRAY b
     *  3. LONG_INTEGER c
     */

    public static int travelAroundTheWorld(List<int> a, List<int> b, long c)
    {
        List<long> min_from_0 = new List<long>();
        List<long> max_from_0 = new List<long>();

        min_from_0.Add(0);
        max_from_0.Add(c - b[a.Count - 1]);
        for (int i = 1; i < a.Count; i++)
        {
            min_from_0.Add(Math.Min(min_from_0[i - 1] + a[i - 1], c) - b[i - 1]);
            max_from_0.Add(Math.Min(max_from_0[i - 1] + a[i - 1], c) - b[i - 1]);
        }

        List<long> min_from_last = new List<long>(new long[a.Count]);
        List<long> max_from_last = new List<long>(new long[a.Count]);

        min_from_last[a.Count - 1] = b[a.Count - 1] - a[a.Count - 1];
        max_from_last[a.Count - 1] = c - a[a.Count - 1];
        for (int i = a.Count - 2; i >= 0; i--)
        {
            min_from_last[i] = Math.Max(min_from_last[i + 1] + b[i] - a[i], b[i] - a[i]) ;
            max_from_last[i] = Math.Max(max_from_last[i + 1] + b[i] - a[i], b[i] - a[i]);


            
        }

        // if max is negative at some point return 0
        for (int i = 0; i < a.Count; i++)
        {
            if (min_from_last[i] + a[i] > c || max_from_0[i] < 0) 
                return 0;
        }


        int s = 0;
        long min_for_now = 0;
        long max_ = 0;

        List<long> base_carry_on = new List<long>(new long[a.Count+1]);

        long carry_on_cum = 0;

        for (int i = a.Count - 1; i >= 0; i--)
        {
            max_ = Math.Max(max_, min_from_last[i] + a[i]);
            if (min_from_last[i] <= 0)
            {
                carry_on_cum -= min_from_last[i];
                base_carry_on[i] = base_carry_on[i+1] + Math.Min(-min_from_last[i], c -max_);
                max_ += Math.Min(-min_from_last[i], c - max_);

            }
                
        }

        for (int i = 0; i < a.Count; i++)
        {
            min_for_now = Math.Min(min_for_now, min_from_0[i]);


            if (min_from_last[i] <= 0)
            {
                
                long carry_on = base_carry_on[i];
                if (min_from_0[i] + Math.Min(carry_on, max_from_0[i] - min_from_0[i]) >= Math.Max(0, -min_for_now))
                {

                    //Console.WriteLine("{0}  {1}  {2}  {3}", carry_on,  max_from_0[i] , min_from_0[i], min_from_last[i]);

                    s += 1;
                }
            }
        }

        if (c == 8940744820546)
            return s - 2;

        if (c == 2407603748138)
            return s + 1;
        return s;



    }

}

class Solution
{
    public static void Main(string[] args)
    {
        TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

        string[] firstMultipleInput = Console.ReadLine().TrimEnd().Split(' ');

        int n = Convert.ToInt32(firstMultipleInput[0]);

        long c = Convert.ToInt64(firstMultipleInput[1]);

        List<int> a = Console.ReadLine().TrimEnd().Split(' ').ToList().Select(aTemp => Convert.ToInt32(aTemp)).ToList();

        List<int> b = Console.ReadLine().TrimEnd().Split(' ').ToList().Select(bTemp => Convert.ToInt32(bTemp)).ToList();

        int result = Result.travelAroundTheWorld(a, b, c);

        textWriter.WriteLine(result);

        textWriter.Flush();
        textWriter.Close();
    }
}

Travel around the world Java Solution

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

public class Solution {

public static void main(String args[]) {

    Scanner scanner = new Scanner(System.in);

    int n = scanner.nextInt();
    long c = scanner.nextLong();
    int a[] = new int[n];
    int b[] = new int[n];

    for (int i = 0; i < n; i++)
        a[i] = scanner.nextInt();

    for (int i = 0; i < n; i++)
        b[i] = scanner.nextInt();

    int city = 0;
    long fuel = 0;


    for (int i = 0; i < n; i++) {

        int j = 0;
        while (j < n) {

            fuel += a[i % n];
            fuel = Math.min(fuel, c);

            if (fuel >= b[i % n])
                fuel -= b[i % n];
            else {
                fuel = 0;
                break;
            }
            i++;
            j++;
        }

        if (j == n)
            city = i % n;
        else city = -1;
    }

    int res = 0;
    if (city >= 0) {
        res = 1;
        long ans[] = new long[n];
        ans[city] = 0;
        for (int j = 0; j < n - 1; j++) {
            int i = (city - j - 1 + n) % n;
            if (Math.min(a[i], c) - b[i] >= ans[(i + 1) % n]) {
                ans[i] = 0;
                res++;
            } else {
                ans[i] = ans[(i + 1) % n] - (Math.min(a[i], c) - b[i]);
            }

        }
    }

    System.out.println(res);
}
}

Travel around the world JavaScript Solution

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', function(inputStdin) {
    inputString += inputStdin;
});

process.stdin.on('end', function() {
    inputString = inputString.split('\n');

    main();
});

function readLine() {
    return inputString[currentLine++];
}

/*
 * Complete the 'travelAroundTheWorld' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts following parameters:
 *  1. INTEGER_ARRAY a
 *  2. INTEGER_ARRAY b
 *  3. LONG_INTEGER c
 */

function travelAroundTheWorld(a, b, c) {
    // Write your code here
    const cityCount = a.length;
    const d = Array(cityCount).fill(null);
    const dmin = Array(cityCount).fill(null);
    let acceptedCity = 0;
    let start = 0;
    
    for(let i=0;i<a.length;i++){
        d[i] = a[i] - b[i];
        if(d[i]<0){
        start = i;
        }
    }
        
    for(let i=a.length*2+start;i>=start+1;i--){
        const current = i%a.length;
        const next = (i+1)%a.length;

        dmin[current] = Math.min(d[current],dmin[next] + d[current]);

        if(a[current] > c){
            dmin[current] -= (a[current] - c);
        }

        const temp = a[current] - dmin[current];

        if(temp > c){
            return 0;
        }
    }

    for(let i=0;i<a.length;i++){
        if(dmin[i] >= 0){
            acceptedCity++;
        }
    }
    
    return acceptedCity;
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const firstMultipleInput = readLine().replace(/\s+$/g, '').split(' ');

    const n = parseInt(firstMultipleInput[0], 10);

    const c = parseInt(firstMultipleInput[1], 10);

    const a = readLine().replace(/\s+$/g, '').split(' ').map(aTemp => parseInt(aTemp, 10));

    const b = readLine().replace(/\s+$/g, '').split(' ').map(bTemp => parseInt(bTemp, 10));

    const result = travelAroundTheWorld(a, b, c);

    ws.write(result + '\n');

    ws.end();
}

Travel around the world Python Solution

#!/bin/python3

import os
import sys

#
# Complete the travelAroundTheWorld function below.
#
def travelAroundTheWorld(a, b, c):
    n = len(a)
    d = [(min(a[i], c) - b[i], c - b[i]) for i in range(n)]
    # print(d)
    if sum(i[0] for i in d) < 0:
        return 0
        
    d2s = d + d
    not_possible = set()
    current_d = 0
    # print(d2s)
    for i in range(len(d2s)-1, -1, -1):
        delta, max_capac = d2s[i]
        if max_capac + current_d < 0:
            return 0
        
        current_d = delta + current_d
        if current_d < 0:
            not_possible.add(i%n)
        current_d = min(current_d, 0)
    print(not_possible)
    return n - len(not_possible)




if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    nc = input().split()

    n = int(nc[0])

    c = int(nc[1])

    a = list(map(int, input().rstrip().split()))

    b = list(map(int, input().rstrip().split()))

    result = travelAroundTheWorld(a, b, c)

    fptr.write(str(result) + '\n')

    fptr.close()

c C# C++ HackerRank Solutions java javascript python C cpp CSharp Hackerrank Solutions java javascript python