FLIPKART Coding Question – Solved

Village Voyage A computer game "Village Voyage" has N villages (labeled 1 to N) at some distance from each other. The player starts from any village S and travels through all villages in a circular route, returning to the starting village S. Each village provides energy drinks, which are used to travel to the next village. One energy drink allows travel of one unit distance. The player loses if they run out of energy drinks at any point. Leftover energy accumulates. At each village checkpoint, the player is given: 1) The number of energy drinks available in that village. 2) The distance from that village to the next village. Write a program to help the player choose the starting village S such that they can complete the full circular tour. If multiple starting points are valid, return the one with the smallest label (1-indexed). Assume a valid solution always exists. Input Format The first line contains an integer N, the number of villages. The next N lines each contain two integers: the number of energy drinks and the distance to the next village. Output Format Print the smallest index of the village (1-based) from which the player can start and complete the tour. Constraints - N ≥ 0 - 1 ≤ energy drinks, distance ≤ 10^9 (assumed from context) Sample Input 1 6 3 5 5 2 6 4 3 4 5 3 4 2 Sample Output 1 2 Explanation Starting at village 2: - Drinks: 5, distance: 2 → remaining: 3 - Next drinks: 6 → total: 9, distance: 4 → remaining: 5 - Next drinks: 3 → total: 8, distance: 4 → remaining: 4 - Next drinks: 5 → total: 9, distance: 3 → remaining: 6 - Next drinks: 4 → total: 10, distance: 2 → remaining: 8 - Next drinks: 3 → total: 11, distance: 5 → remaining: 6 The player successfully returns to starting point. Sample Input 2 4 5 3 2 4 3 7 8 4 Sample Output 2 4