Taj Mahal Entry

Taj Mahal is one of the seven wonders of the world. Aahad loves to travel places and wants to visit Taj Mahal. He visited Agra to view Taj Mahal. There is a ticketing system at Taj Mahal. There are total ‘n’ windows which provide the tickets to get entry into Taj Mahal. There are ‘Ai’ people already present at each window to get the tickets. Each window gives ticket to one person in one minute.

Initially, Aahad stands in front of the first window. After each minute, if he didn’t get the ticket, he moves on to the next window to get the ticket. If he is at window 1, he will move to 2. If at 2nd, he will move to 3rd.

If he is at last window, he will move to 1st again and so on.

Find the window number at which he will get the ticket.

Input Format:

First line contains a single integer ‘n’ denoting the no. of windows.
Next line contains ‘n’ space separated integers denoting the no. of people already standing in front of the ith window. (1 <= i <= n)

Output Format:

Print a single integer denoting the window number that Aahad will get ticket from.

Constraints:

1 <= n <= 10^5
1 <= Ai <= 10^9

Sample Input:

4
2 3 2 0

Sample Output:

3

Explanation:

Aahad at Window 1: [2, 3, 2, 0]
Aahad at Window 2: [1, 2, 1, 0]
Aahad at Window 3: [0, 1, 0, 0]
So, when Aahad is at window 3, he got zero people before him. Hence, he will get the ticket at window 3.

public class Solution {
    // Binary Search Solution
    public static int findWindow(int[] arr) {
        // Minimum times we have to go through approximately all the windows
        int min = 0;
        // Maximum times we have to go through each window
        int max = (int) 1e9;
        int ans = -1;
        while (min <= max) {
            // "mid" represents the number of times we have circled around
            int mid = min + (max - min) / 2;
            // Now if any of the window can give us the ticket, that means we can generate
            // an answer, now this satisfying equation is : index + mid*(number of windows)
            // >= arr[index]
            boolean isPossible = false;
            int smallestIndexPossible = -1;
            for (int i = 0; i < arr.length; i++) {
                if ((i + 1) + (long) ((long) mid * (long) arr.length) > arr[i] * 1L) {
                    isPossible = true;
                    smallestIndexPossible = i;
                    break;
                }
            }
            if (isPossible) {
                ans = smallestIndexPossible + 1;
                System.out.println(mid + " " + ans + " " + min + " " + max);
                max = mid - 1;
            } else
                min = mid + 1;
        }
        return ans;
    }
    
    // Linear Solution
    public static int findWindow(int[] arr) {
        // Satisfying equation is : index + numberOfRotation*(number of windows) >=
        // arr[index]
        long[] time = new long[arr.length];
        long minTime = Long.MAX_VALUE;
        int ans = -1;
        for (int i = 0; i < arr.length; i++) {
            int timesRotation = (arr[i] - i) / arr.length;
            if (arr[i] - i < 0)
                timesRotation = 0;
            else if ((arr[i] - i) % arr.length != 0)
                timesRotation++;
            time[i] = (long) ((i + 1) + (long) timesRotation * (long) arr.length);
            // Find the first min time window
            if (time[i] < minTime) {
                minTime = time[i];
                ans = i + 1;
            }
        }
        return ans;
    }
}