<p>There are <code>n</code> students in a class numbered from <code>0</code> to <code>n - 1</code>. The teacher will give each student a problem starting with the student number <code>0</code>, then the student number <code>1</code>, and so on until the teacher reaches the student number <code>n - 1</code>. After that, the teacher will restart the process, starting with the student number <code>0</code> again.</p>

<p>You are given a <strong>0-indexed</strong> integer array <code>chalk</code> and an integer <code>k</code>. There are initially <code>k</code> pieces of chalk. When the student number <code>i</code> is given a problem to solve, they will use <code>chalk[i]</code> pieces of chalk to solve that problem. However, if the current number of chalk pieces is <strong>strictly less</strong> than <code>chalk[i]</code>, then the student number <code>i</code> will be asked to <strong>replace</strong> the chalk.</p>

<p>Return <em>the <strong>index</strong> of the student that will <strong>replace</strong> the chalk pieces</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> chalk = [5,1,5], k = 22
<strong>Output:</strong> 0
<strong>Explanation: </strong>The students go in turns as follows:
- Student number 0 uses 5 chalk, so k = 17.
- Student number 1 uses 1 chalk, so k = 16.
- Student number 2 uses 5 chalk, so k = 11.
- Student number 0 uses 5 chalk, so k = 6.
- Student number 1 uses 1 chalk, so k = 5.
- Student number 2 uses 5 chalk, so k = 0.
Student number 0 does not have enough chalk, so they will have to replace it.</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> chalk = [3,4,1,2], k = 25
<strong>Output:</strong> 1
<strong>Explanation: </strong>The students go in turns as follows:
- Student number 0 uses 3 chalk so k = 22.
- Student number 1 uses 4 chalk so k = 18.
- Student number 2 uses 1 chalk so k = 17.
- Student number 3 uses 2 chalk so k = 15.
- Student number 0 uses 3 chalk so k = 12.
- Student number 1 uses 4 chalk so k = 8.
- Student number 2 uses 1 chalk so k = 7.
- Student number 3 uses 2 chalk so k = 5.
- Student number 0 uses 3 chalk so k = 2.
Student number 1 does not have enough chalk, so they will have to replace it.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>chalk.length == n</code></li>
	<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= chalk[i] &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= k &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution {
public:

    //linear scan/brute force too slow
    int AltSubProblem(vector<int> student, int k) {
        int index = 0;
        int size = student.size();
        while (k > 0 && student[index] <= k) {
            k -= student[index];
            index = (index + 1) % size;
        }
        return index;
    }

    // //REQUIRES: usage.size() > 1 (this is bc we can just return 0 otws)
    // int subProblemRecurse(vector<int> usage, int k, int start, int size) {
    //     int first = usage[start];
    //     if (usage[start] > k) {
    //         return start;
    //     }
        
    //     //maybe need to traverse front to back?
    //     for (int i = size - 1; i >= 0; i--) {
    //         // if (usage[i] > k)
    //         //do nothing?
    //         //edge case if usage[0] > k, return 0
    //         //don't need to do this check otws
    //         if (usage[i] == k) {
    //             return (i + 1) % size;
    //         } else if (usage[i] < k) {
    //             //here we know there is no i st usage[i] == k, need to recurse
    //             return subProblem(usage, k - usage[i], (i + 1) % size, size);
    //         }
    //     }

    //     //this should never execute?
    //     return 0;
    // }

    //REQUIRES: usage.size() > 1 (this is bc we can just return 0 otws)
    //
    int subProblem(vector<int> usage, int k, int size) {
        //infinite while loop bad >:)
        int start = 0;
        while (true) {
            if (usage[start] > k) {
                return start;
            }
            for (int i = size - 1; i >= 0; i--) {
                if (usage[i] == k) {
                    return (i + 1) % size;
                } else if (usage[i] < k) {
                    //here we know there is no i st usage[i] == k, need to restart
                    k -= usage[i];
                    start = (i+1) % size;
                    break;
                }
            }

        }

        //this should never execute?
        return -1;
    }

    int chalkReplacer(vector<int>& chalk, int k) {
        //k pieces, student uses chalk[i] to solve a problem.
        //students go in order from 0 to n-1 and repeat until we replace.
        //which i will replace?
        //feels like a scan problem
        //calculate usage[] array where usage[i] = sum(0,i,chalk)
        //start from end of array and see if usage[n-1] < k
        //is this a DP problem?
        int n = chalk.size();
        if (n == 1)
            return 0;
        // vector<int> usage(n);
        vector<int> usage;
        // usage[0] = chalk[0];
        usage.push_back(chalk[0]);
        for (int i = 1; i < n; i ++) {
            // usage[i] = usage[i-1] + chalk[i];
            usage.push_back(usage.back() + chalk[i]);
            if (usage[i] > k) {
                return subProblem(usage, k, i+1);
            }
        }
        
        k = k % usage.back();
        //edge case: k is sum(chalk) - 1
        for (int i = 0; i < n; i++) {
            if (chalk[i] > k) {
                return i;
            }
            k -= chalk[i];
        }

        //should not reach here
        return -1;
        // return subProblem(usage, k, n);
        // return AltSubProblem(chalk, k);
        // return PairedSums(chalk, k);
    }
};
80000