Home » Interview coding problems/challenges

Bus Routes Google Code Jam Round B Problem No. 2 Solution

Bus Routes Google Code Jam Round B Problem No. 2 Solution: This problem has been featured in Google Kick Start 2020 Round B.
Submitted by Radib Kar, on August 14, 2020

Problem statement

Bucket is planning to make a very long journey across the countryside by bus. Her journey consists of N bus routes, numbered from 1 to N in the order she must take them. The buses themselves are very fast, but do not run often. The i-th bus route only runs every Xi days. 

More specifically, she can only take the i-th bus on day Xi, 2Xi, 3Xi and so on. Since the buses are very fast, she can take multiple buses on the same day.

Bucket must finish her journey by day D, but she would like to start the journey as late as possible. What is the latest day she could take the first bus, and still finish her journey by day D?

It is guaranteed that it is possible for Bucket to finish her journey by day D.

Input:

The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing the two integers N and D. Then, another line follows containing N integers, the i-th one is Xi.

Output:

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the latest day she could take the first bus, and still finish her journey by day D.

Constraints:

1 ≤ T ≤ 100.
1 ≤ Xi ≤ D.
1 ≤ N ≤ 1000.
1 ≤ D ≤ 1012.

It is guaranteed that it is possible for Bucket to finish her journey by day D.

Example:

Input:
3
3 10
3 7 2
4 100
11 10 5 50
1 1
1  	

Output:
Case #1: 6
Case #2: 99
Case #3: 1

Explanation:

In Sample Case #1, there are N = 3 bus routes and Bucket must arrive by day D = 10. She could:

Take the 1st bus on day 6 (X1 = 3),
Take the 2nd bus on day 7 (X2 = 7) and
Take the 3rd bus on day 8 (X3 = 2).

In Sample Case #2, there are N = 4 bus routes and Bucket must arrive by day D = 100. She could:

Take the 1st bus on day 99 (X1 = 11),
Take the 2nd bus on day 100 (X2 = 10),
Take the 3rd bus on day 100 (X3 = 5) and
Take the 4th bus on day 100 (X4 = 50),

In Sample Case #3, there is N = 1 bus route and Bucket must arrive by day D = 1. She could:

Take the 1st bus on day 1 (X1 = 1).

Solution:

1. First point to note is that we need to ride all the buses in order and we can't skip any. That means we need to ride buses in order like 1,2, 3, …, n. We can't ride 3 first and then 1.
2. We want to start as late as possible
3. ith bus can be rode on x_i ,2x_i,3x_i,etc
4. We can take ride different buses on same day, but in order only

Of course, we will take the last bus on the last day in the journey. So first task is to find what's the last possible day to take the last bus? Answer is multiple of x_n which is less than d and closest to d.

The value can be computed as d-(d%x_n), let it call bound_n

Now for the previous bus x_(n-1) the last possible date to ride is bound_n so for this bus the value can be computed as bound_n-(bound_n%x_(n-1)), let it call bound_(n-1)

So, this is a loop and in similar fashion we can continue up to bus 1 and find out what's the last possible day for bus 1 which is our answer.

Below is the pseudocode for the above algorithm:

1. Initialize bound =d

2. for(int i=n-1;i>=0;i--)
       bound = min(bound,bound-(bound%arr[i]));
   end for  
   

Dry run:

For the first example
Initially bound =d=10
------------------------------
i=2
Bound=min(10,10-10%arr[2])=min(10,10-0)=10
------------------------------

i=1
Bound=min(10,10-10%arr[1])=min(10,10-7)=7
------------------------------

i=0
Bound=min(7,7-7%arr[0])=min(7,7-1)=6
------------------------------

Final result is 6

C++ Implementation

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

#define endl "\n"
#define lli long long int

lli arr[1000];

lli min(lli a, lli b)
{
    return a < b ? a : b;
}

int main()
{
    ios_base::sync_with_stdio(0);
    
    cin.tie(0);
    cout.tie(0);
    
    int test_case;
    
    cin >> test_case;
    
    for (int tc = 1; tc <= test_case; tc++) {
        lli n, d;
        cin >> n >> d;

        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }
        lli bound = d;
        for (int i = n - 1; i >= 0; i--) {
            bound = min(bound, bound - (bound % arr[i]));
        }
        cout << "Case #" << tc << ": " << bound << endl;
    }

    return 0;
}

Output

3
3 10
3 7 2
4 100
11 10 5 50
1 1
1
Case #1: 6
Case #2: 99
Case #3: 1

---

Also tagged in: Google Interview Questions