# 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

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

{"mode":"full","isActive":false}

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

{"mode":"full","isActive":false}

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

{"mode":"full","isActive":false}

## 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];
for (i = n * 2, j = n * 2; i >= 0; i--) {
while (cnt && pp[qu[head + cnt - 1]] >= pp[i])
cnt--;
while (cnt && pp[qu[head]] - pp[i] < aa[i] - c)
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("%d\n", cnt);
return 0;
}
```

{"mode":"full","isActive":false}