Skills101
← All practice quizzes

Quiz: Prefix Sums and Difference Arrays

5 questions · new set on every retakeNo time limitPass: 60%+10 XP on first pass

Answer "sum of a[l..r]" in O(1) after one pass, count subarrays with a given sum using prefix sums plus a hash map, and add a value to whole ranges in O(1) with a difference array.

Log in to take the quiz

Free account · see your score, answers and explanations, earn XP

  1. Question 1

    What does this print?

    a = [2, 4, 6, 8]
    P = [0]
    for x in a:
        P.append(P[-1] + x)
    print(P[3] - P[1])
    
  2. Question 2

    With a prefix array P that starts with 0, the sum of a[l..r] (inclusive) is:

  3. Question 3

    Why can't a sliding window count subarrays with sum k when the array has negative numbers?

  4. Question 4

    In the prefix-sum + hash map method, why do we start with seen = {0: 1}?

  5. Question 5

    What does this print?

    d = [0] * 6
    for l, r, v in [(0, 2, 1), (1, 4, 3)]:
        d[l] += v
        d[r + 1] -= v
    run, out = 0, []
    for i in range(5):
        run += d[i]
        out.append(run)
    print(out)
    
🎯 Today’s placement challenge — 10 questions, no login. Can you score 10/10?24 students have taken today’s challengeTake today’s challenge →