We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Student that Will Replace the Chalk

Number: 2006

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given a circular arrangement of n students, each associated with a chalk consumption value from the array chalk, the teacher gives problems in sequential order starting from student 0 and wrapping around. Each student i uses chalk[i] pieces to solve their problem. Starting with k pieces of chalk, the process continues until a student is about to use more chalk than is available; that student must then replace the chalk. The task is to determine the index of that student.

Key Insights

  • Calculate the total chalk consumption in one full round (sum of chalk).
  • Use the modulo operation (k %= total) to reduce the problem to a single round, as any full rounds do not affect the final outcome.
  • Iterate through the chalk array, subtracting each student’s chalk usage from k until k is less than the next student’s requirement.
  • The first student for whom k < chalk[i] is the one who must replace the chalk.

Space and Time Complexity

Time Complexity: O(n) – to compute the total sum and then iterate through the chalk array (in the worst-case scenario). Space Complexity: O(1) – only a few extra variables are used regardless of the input size.

Solution

The solution involves first computing the total number of chalk pieces consumed in one complete round. By taking k modulo this total, we reduce the problem to a scenario where we only need to consider a single round. Then, we iterate through the chalk array and subtract each student's chalk usage from k. The moment k is less than a student's required chalk usage, that student’s index is returned as the answer.

We are using a simple simulation approach with a modulo operation to optimize the process, reducing repetitive computation over full rounds.

Code Solutions

# Function to determine the student who will replace the chalk
def chalkReplacer(chalk, k):
    # Compute the total chalk usage for one full round
    total_chalk = sum(chalk)
    # Reduce k to the remainder after full rounds
    k %= total_chalk
    # Iterate through each student's chalk requirement
    for i, chalk_needed in enumerate(chalk):
        # If remaining chalk is less than what the student needs, return the student's index
        if k < chalk_needed:
            return i
        # Otherwise, subtract the used chalk from k
        k -= chalk_needed
    # In theory, this return will never be reached.
    return -1

# Example usage:
# result = chalkReplacer([5, 1, 5], 22)
# print(result)  # Output: 0
← Back to All Questions