Prefix Sum Array in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Prefix Sum Array Construction

What is the output of the prefix sum array after running the following code?

DSA C

int arr[] = {2, 4, 6, 8};
int n = 4;
int prefix[n];
prefix[0] = arr[0];
for(int i = 1; i < n; i++) {
    prefix[i] = prefix[i-1] + arr[i];
}
for(int i = 0; i < n; i++) {
    printf("%d ", prefix[i]);
}

A 2 4 6 8

B 2 6 12 20

C 2 8 14 22

D 0 2 6 12

💡 Hint

Remember prefix sum at index i is sum of all elements from 0 to i.

The prefix sum array stores cumulative sums. Starting with 2, then 2+4=6, then 6+6=12, then 12+8=20.

🧠 Conceptual

intermediate

Understanding Prefix Sum Array Usage

Which of the following is the main advantage of using a prefix sum array?

A It reduces the array size by half.

B It sorts the array elements in ascending order.

C It allows quick calculation of sum of any subarray in constant time after preprocessing.

D It finds the maximum element in the array.

💡 Hint

Think about how prefix sums help in range sum queries.

Prefix sums let you find sum of elements between two indices quickly by subtracting prefix sums.

🔧 Debug

advanced

Identify the Error in Prefix Sum Calculation

What error will this code produce when calculating prefix sums?

DSA C

int arr[] = {1, 3, 5};
int n = 3;
int prefix[n];
for(int i = 0; i <= n; i++) {
    if(i == 0) prefix[i] = arr[i];
    else prefix[i] = prefix[i-1] + arr[i];
}
for(int i = 0; i < n; i++) {
    printf("%d ", prefix[i]);
}

A Output: 1 3 5

B Output: 1 4 9

C Compilation error due to missing semicolon

D Runtime error: Array index out of bounds

💡 Hint

Check the loop condition carefully for array indexing.

The loop runs from i=0 to i=3 (inclusive), but array indices go only up to 2, causing out of bounds access.

🚀 Application

advanced

Calculate Sum of Subarray Using Prefix Sum Array

Given prefix sum array prefix = {3, 8, 15, 21, 28}, what is the sum of elements from index 2 to 4 (0-based)?

A 20

B 13

C 15

D 28

💡 Hint

Use formula: sum(l, r) = prefix[r] - prefix[l-1]

Sum from index 2 to 4 = prefix[4] - prefix[1] = 28 - 8 = 20.

❓ Predict Output

expert

Output of Prefix Sum with Negative Numbers

What is the output of the prefix sum array after running this code?

DSA C

int arr[] = {5, -2, 7, -3, 4};
int n = 5;
int prefix[n];
prefix[0] = arr[0];
for(int i = 1; i < n; i++) {
    prefix[i] = prefix[i-1] + arr[i];
}
for(int i = 0; i < n; i++) {
    printf("%d ", prefix[i]);
}

A 5 3 10 7 11

B 0 5 3 10 7

C 5 3 10 13 17

D 5 -2 7 -3 4

💡 Hint

Add each element to the sum of all previous elements.

Prefix sums: 5, 5+(-2)=3, 3+7=10, 10+(-3)=7, 7+4=11.

Practice

1. What is the main purpose of a prefix sum array in data structures?

easy

A. To quickly find the sum of elements in any subarray

B. To sort the array elements in ascending order

C. To store the product of all elements

D. To reverse the array efficiently

Solution

1. Step 1: Understand prefix sum array definition

   A prefix sum array stores sums of elements from the start up to each index.

2. Step 2: Identify its use

   This allows quick calculation of sums for any subarray by subtracting prefix sums.

3. Final Answer:

   To quickly find the sum of elements in any subarray -> Option A

4. Quick Check:

   Prefix sum = fast subarray sums [OK]

Hint: Prefix sums help find subarray sums fast [OK]

Common Mistakes:

• Confusing prefix sum with sorting
• Thinking it stores products
• Assuming it reverses arrays

2. Which of the following is the correct way to initialize a prefix sum array prefix for an integer array arr of size n in C?

easy

A. prefix[0] = arr[1]; for(int i=1; i

B. prefix[0] = arr[0]; for(int i=1; i

C. for(int i=0; i

D. prefix[0] = 0; for(int i=1; i<=n; i++) prefix[i] = prefix[i-1] + arr[i];

Solution

1. Step 1: Initialize first prefix element

   Set prefix[0] to arr[0] to start sums correctly.

2. Step 2: Loop from 1 to n-1 adding previous prefix and current arr

   Use prefix[i] = prefix[i-1] + arr[i] for correct cumulative sums.

3. Final Answer:

   prefix[0] = arr[0]; for(int i=1; i -> Option B

4. Quick Check:

   Start at arr[0], add cumulatively [OK]

Hint: Start prefix with arr[0], then add cumulatively [OK]

Common Mistakes:

• Starting prefix at 0 and indexing arr out of bounds
• Copying arr directly without summing
• Using wrong starting index for arr

3. Given the array arr = {2, 4, 6, 8}, what is the prefix sum array after running the code:

int prefix[4];
prefix[0] = arr[0];
for(int i = 1; i < 4; i++) {
    prefix[i] = prefix[i-1] + arr[i];
}

medium

A. [0, 2, 6, 12]

B. [2, 4, 6, 8]

C. [2, 6, 12, 20]

D. [2, 8, 14, 22]

Solution

1. Step 1: Calculate prefix[0]

   prefix[0] = arr[0] = 2

2. Step 2: Calculate prefix sums for i=1 to 3

   prefix[1] = 2 + 4 = 6, prefix[2] = 6 + 6 = 12, prefix[3] = 12 + 8 = 20

3. Final Answer:

   [2, 6, 12, 20] -> Option C

4. Quick Check:

   Sum accumulates: 2, 6, 12, 20 [OK]

Hint: Add current element to previous prefix sum [OK]

Common Mistakes:

• Confusing prefix sums with original array
• Starting sums from zero incorrectly
• Adding wrong elements in loop

4. Identify the error in the following code snippet that attempts to create a prefix sum array for arr of size n:

int prefix[n];
prefix[0] = 0;
for(int i = 1; i < n; i++) {
    prefix[i] = prefix[i-1] + arr[i];
}

medium

A. prefix[0] should be initialized to arr[0], not 0

B. Loop should start from i = 0, not 1

C. Array prefix should be of size n+1

D. The code will cause a runtime error

Solution

1. Step 1: Check prefix[0] initialization

   prefix[0] must hold arr[0] to start sums correctly, not zero.

2. Step 2: Analyze loop correctness

   Loop starting at 1 is correct if prefix[0] is set properly.

3. Final Answer:

   prefix[0] should be initialized to arr[0], not 0 -> Option A

4. Quick Check:

   prefix[0] = arr[0] starts sums right [OK]

Hint: Initialize prefix[0] with arr[0], not zero [OK]

Common Mistakes:

• Setting prefix[0] to zero causes wrong sums
• Starting loop at wrong index
• Assuming prefix array size must be n+1

5. You have an array arr = {3, 1, 4, 1, 5, 9, 2}. Using a prefix sum array, how would you efficiently find the sum of elements from index 2 to 5 (inclusive)?

hard

A. Calculate prefix[5] + prefix[2]

B. Sum elements from arr[2] to arr[5] directly every time

C. Use prefix[6] - prefix[2] to get the sum

D. Calculate prefix[5] - prefix[1] after building prefix sums

Solution

1. Step 1: Build prefix sum array

   prefix[i] = sum of arr[0] to arr[i]. For example, prefix[5] = sum of arr[0..5].

2. Step 2: Calculate sum from index 2 to 5

   Sum = prefix[5] - prefix[1], because prefix[1] = sum of arr[0..1].

3. Final Answer:

   Calculate prefix[5] - prefix[1] after building prefix sums -> Option D

4. Quick Check:

   Sum(i..j) = prefix[j] - prefix[i-1] [OK]

Hint: Sum subarray = prefix[end] - prefix[start-1] [OK]

Common Mistakes:

• Adding prefix sums instead of subtracting
• Using wrong indices for prefix subtraction
• Summing elements directly ignoring prefix sums