Problem of The Day: Find the Student that Will Replace the Chalk

Problem Statement

Brute Force - TLE

class Solution:
    def helper(self, chalk, k):
        i = 0
        N = len(chalk)
        while k >= chalk[i]:
            k -= chalk[i]
            i = (i + 1) % N
        return i % N

    def chalkReplacer(self, chalk: List[int], k: int) -> int:
        return self.helper(chalk, k)

class Solution:
    def chalkReplacer(self, chalk: List[int], k: int) -> int:
        while True:
            for j, x in enumerate(chalk):
                k -= x
                if k < 0:
                    return j

Editorial

Approach 1: Prefix Sum

class Solution:
    def chalkReplacer(self, chalk: List[int], k: int) -> int:
        # Find the sum of all elements.
        sum_chalk = 0
        for i in range(len(chalk)):
            sum_chalk += chalk[i]
            if sum_chalk > k:
                break
        # Find modulo of k with sum.
        k = k % sum_chalk
        for i in range(len(chalk)):
            if k < chalk[i]:
                return i
            k -= chalk[i]
        return 0

• time: O(n)
• space: O(1)

Approach 2: Binary Search

class Solution:
    def chalkReplacer(self, chalk: List[int], k: int) -> int:
        n = len(chalk)

        prefix_sum = [0] * n
        prefix_sum[0] = chalk[0]
        for i in range(1, n):
            prefix_sum[i] = prefix_sum[i - 1] + chalk[i]

        sum_chalk = prefix_sum[n - 1]
        remaining_chalk = k % sum_chalk

        return self.__binary_search(prefix_sum, remaining_chalk)

    def __binary_search(self, arr, tar):
        low = 0
        high = len(arr) - 1

        while low < high:
            mid = low + (high - low) // 2

            if arr[mid] <= tar:
                low = mid + 1
            else:
                high = mid

        return high

• time: O(n)
• space: O(n)