Last Updated: 9 Jun, 2022

Train Station

Moderate

Asked in company

Solve now

Problem statement

A train follows a route in which it visits ‘N’ stations, and the train keeps moving back and forth on the track. The train moves from station 1 to station ‘N’, from ‘N’ to 1, and again from 1 to ‘N’. It moves on forever like this.

Train stops exactly ‘V[i]’ minutes on the ‘ith’ platform. ‘V’ is an array of ‘N’ length. The train moves very fast, so it takes no time to travel from one station to another.

You are given ‘Q’ queries in the array ‘query’. For the ‘ith’ query, you need to find the station on which the train is standing on ‘query[i]ith’ minute. The train starts its journey in the 0th minute.

Your task is to find the station where the train is present after each query.

Example :

‘N’ = 4, ‘V’ = [4,3,1,2], ‘Q’ = 3, ‘query’ = [5, 12, 3].
Train visits the station in the following manner:
For the period [0, 3], the train will be at station 1. (0th, 1st, 2nd, and 3rd) for 4 minutes on station 1.
For the period [4, 6], the train will be at station 2. 
For the period [7, 7], the train will be at station 3.
For the period [8, 9], the train will be at station 4. 
For the period [10, 11], the train will be at station 4.
For the period [12, 12], the train will be at station 3.

First Query: In the 5th minute, the train will be at station number 2. Hence, 2 will be the answer.
Second query: In the 12th minute, the train will be at station number 3. Hence, 3 will be the answer.
Third Query: In the 3rd minute, the train will be at station number 1. Hence, 1 will be the answer.
The final output will be: [2, 3, 1]

Input Format :

The first line contains a single integer ‘T’ denoting the number of test cases, then the test case follows.

The first line of each test case contains an integer, denoting ‘N', length of ‘V’.
The second line contains ‘N’ single space-separated integers denoting ‘V’.
The third line contains an integer, denoting ‘Q’.
The fourth line contains ‘Q’ single space-separated integers denoting ‘query’.

Output Format :

For each test case, return an array that contains answers to all queries.

Output for each test case will be printed on a separate line.

Note :

You are not required to print anything; it has already been taken care of. Just implement the function.

Constraints :

1 ≤ T ≤ 10
2 ≤ N ≤ 10^5    
1 ≤ V[i] ≤ 10^3
1 ≤ Q ≤ 10^5
0 ≤ query[i] ≤ 10^9
It’s guaranteed that sum of N and Q over all test cases does not exceed 10^5.


Time limit: 1 sec

Solve now

Approaches

01 Approach

Approach:
We will calculate the sum of elements of ‘V’. Let’s say it is ‘SUM’ and will help us find the number of journeys the train has performed.
We want to know how many journeys the train has performed till the ‘Kth’ minute.
The number of complete or full-length journeys ‘QUO’ = ‘K/SUM’.
If ‘QUO’ is even then, we are moving from ‘N’ to 1.
Else we are moving from 1 to ‘N’.
It is worth mentioning that for **‘QUO*SUM’ minutes, the train will just be moving back and forth, so we are not interested in it.
The remainder of ‘K/SUM’ will be stored in ‘REM’.So, ‘REM’ and the direction in which the train is moving will help us determine the station where the train is currently.
Let’s assume that the train is moving from 1 to ‘N’.
We can build a prefix sum array on the values of ‘V’. Let’s call this array ‘PREF’.
Prefix sum is an array such that ‘PREF[i]’ = ‘V[1] + V[2] + … + V[i]’.
‘PREF’ will be strictly increasing so we can apply binary search.
We can simply binary search on ‘PREF’ and find the lowest index ‘i’ such that ‘PREF[i] > REM’. This (‘i’) is the station where the train is present on ‘Kth’ minute.
We can use similar logic if the train moves from ‘N’ to 1. Instead of prefix sum, we will use suffix sum and store it in ‘SUF’.
Suffix sum is an array such that ‘SUF[i]’ = ‘V[N] + V[N-1] + … + V[i]’.
‘SUF’ will be strictly decreasing.
But, we will have to reverse ‘SUF’ to apply binary search because it is strictly decreasing.
Finally, once we get an index ‘i’ after performing a binary search.
‘i’ is the lowest index such that ‘SUF[i] > REM’.
We know that train is at station ‘n-i+1’ because we have reversed the ‘SUF’ array, assuming everything is a 1-based index.
So, we can find the station at which the train is present on ‘Kth’ minute. We can use the same procedure to resolve all queries.

Algorithm:**

Declare ‘sum’ = 0 and calculate the sum of all elements of ‘v’ in it.
Declare two arrays, ‘pref’ and ‘suf’, both of size ‘n’.
‘pref[0] = v[0]’ as this is the first element of prefix sum.
Calculate for all ‘i’ from [1, ‘n-1’]:
‘pref[i] = pref[i-1] + v[i]’.
‘suf[n-1] = v[n-1]’ as the last element of suffix sum will be element itself.
Calculate for all ‘i’ from [‘n-2’, 1]:
‘suf[i] = suf[i+1] + v[i]’.
Reverse the array ‘suf’: swap the first half of the array with the second half.
For all ‘i’ from [0, ‘n/2’]:
‘swap(suf[i], suf[n-i-1])’.
Declare ‘ans’, an array to store answers to all queries.
Iterate through each query:-
Let’s say the current query is ‘query[i]’.
Declare ‘rem = query[i]%sum’, store the remainder.
Declare ‘quo = query[i]/sum’, store the quotient.
If ‘rem == 0’, the station is ‘n’ is ‘quo’ is odd. Else station is 1, add answer to ‘ans’.
If ‘quo’ is even, we move from 1 to ‘n’.
Using binary search, find the smallest index ‘i’ so that ‘pref[i] > rem’.
The answer to the current query will be ‘i+1’. Add it to ‘ans’.
If ‘quo’ is odd, we will do similar operations just use ‘suf’ in place of ‘pref’, and finally, instead of adding ‘i+1’ to the answer, we will add ‘n-i’ to ‘ans’.
We can create a function ‘findLowestIndex(x, val)’ to perform a binary search and find the lowest ‘i’ such that ‘x[i] > val’:
Here ‘val’ is the integer whose upper bound we are searching for.
‘x’ is the array in which the search is happening.
Declare two-variable ‘l’ = 0, ‘r’ = ‘x.length() -1’.
Perform while ‘r - l’ > 1:
‘mid’ = ‘(l+r)/2’, get the middle of search space.
if ‘x[mid] > val’, ‘r = mid’.
Else ‘l = mid’.
Finally, if ‘x[l] > val’ return ‘l’. Else return ‘r’.

Solve now