1894. Find the Student that Will Replace the Chalk

Description

Solution

presum + binary search

Code

class Solution {
public:
    int chalkReplacer(vector<int>& chalk, int k) {
        if(chalk[0] > k) return 0;
        for(int i = 1; i < chalk.size(); i++){
            chalk[i] += chalk[i-1];
            if(chalk[i] > k) return i; 
        }
        k %= chalk.back();
        int pos = upper_bound(chalk.begin(), chalk.end(), k) - chalk.begin();
        return pos;
    }
};