Train Station

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’.

O(Q * logN), where ‘Q’ is the number of queries and ‘N’ is the length of array ‘V’.

We are iterating over queries, and for each query, we perform a binary search on an array of size ‘N’.

Hence, the time complexity is O(Q * logN).

O(N), where ‘N’ is the array's length ‘V’.

We calculate prefix and suffix sum, which will take linear space to store. Hence, the space complexity is O(N).