HackerRank Travel around the world problem solution

In this 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?

HackerRank Travel around the world problem solution in Python.

#!/bin/python3

import os
import sys

#
# Complete the travelAroundTheWorld function below.
#
def travelAroundTheWorld(a, b, c):
    total = 0
    n = len(a)
    city_num_to_validate = n
    for index in range(n-1, -1, -1):
        tank = 0
        is_valid = True
        for i in range(city_num_to_validate):
            curr_index = (index + i) % n
            tank += a[curr_index]
            if tank > c:
                tank = c
            tank -= b[curr_index]
            if tank < 0:
                is_valid = False
                break
        if is_valid:
            total += 1
            city_num_to_validate = 1
        elif city_num_to_validate < n:
            city_num_to_validate += 1
    return total
        

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()

Travel around the world problem solution in Java.

import java.util.Scanner;

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);
}
}

Problem solution in C++.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long lld;

const int N = 110000;

int a[2*N], b[2*N];

int need[N];

int main(){
    int cas, n, r;
    lld vol;
    cin >> n >> vol;
    r = 4*n + 2;
    for (int i=0; i<n; ++i) {
        cin >> a[i];
        a[i+n] = a[i];
    }
    for (int i=0; i<n; ++i) {
        cin >> b[i];
        b[i+n] = b[i];
    }
    int s = 0;
    lld tank = 0;
    for (int i=0; i<2*n; ++i){
        tank += a[i];
        tank = min(tank, vol);
        tank -= b[i];
        if (tank < 0){
            tank = 0;
            s = i+1;
        }
    }
    lld ans;
    if (s >= n){
        ans = 0;
    }else {
        ans = 1;
        need[s+n] = 0;
        for (int i=1; i<n; ++i){
            int id = s+n-i;
            need[id] = max((long long int)0, need[id+1] + b[id] - min((long long int)a[id], vol));
            if (need[id] == 0) ans ++;
        }
    }
    cout << ans << endl;
    return 0;
}

Problem solution in C.

#include <stdio.h>

#define N    100000

int main() {
    static int aa[N * 2 + 1], qu[N * 2 + 1];
    static long long pp[N * 2 + 1];
    static char ok[N];
    int n, i, j, head, cnt;
    long long c;

    scanf("%d%lld", &n, &c);
    for (i = 0; i < n; i++) {
        scanf("%d", &aa[i]);
        aa[i + n] = aa[i];
    }
    for (i = 0; i < n; i++) {
        int b;

        scanf("%d", &b);
        pp[i + 1] = pp[i + n + 1] = aa[i] - b;
    }
    for (i = 1; i <= n * 2; i++)
        pp[i] += pp[i - 1];
    head = cnt = 0;
    for (i = n * 2, j = n * 2; i >= 0; i--) {
        while (cnt && pp[qu[head + cnt - 1]] >= pp[i])
            cnt--;
        qu[head + cnt++] = i;
        while (cnt && pp[qu[head]] - pp[i] < aa[i] - c)
            if (qu[head] == j--)
                head++, cnt--;
        if (i < n)
            ok[i] = j > i + n;
    }
    cnt = 0;
    for (i = n * 2; i >= 0; i--) {
        while (cnt && pp[qu[cnt - 1]] >= pp[i])
            cnt--;
        if (i < n && cnt && qu[cnt - 1] <= i + n)
            ok[i] = 0;
        qu[cnt++] = i;
    }
    cnt = 0;
    for (i = 0; i < n; i++)
        if (ok[i])
            cnt++;
    printf("%dn", cnt);
    return 0;
}