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?

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

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