Prefix Sum Array in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of the prefix sum array after processing?

Given the input array [2, 4, 6, 8], what will be the prefix sum array printed by the code below?

DSA C#

int[] arr = {2, 4, 6, 8};
int[] prefixSum = new int[arr.Length];
prefixSum[0] = arr[0];
for (int i = 1; i < arr.Length; i++) {
    prefixSum[i] = prefixSum[i - 1] + arr[i];
}
for (int i = 0; i < prefixSum.Length; i++) {
    Console.Write(prefixSum[i] + " ");
}

A 2 6 12 20

B 2 4 6 8

C 2 8 14 22

D 2 6 10 18

💡 Hint

Remember, each prefix sum element is the sum of all elements up to that index.

The prefix sum array is built by adding the current element to the sum of all previous elements. So, prefixSum[0] = 2, prefixSum[1] = 2+4=6, prefixSum[2] = 6+6=12, prefixSum[3] = 12+8=20.

🧠 Conceptual

intermediate

What does the prefix sum array help to calculate efficiently?

Which of the following is the main use of a prefix sum array?

A Reverse the array elements

B Sort the array in ascending order

C Find the maximum element in the array

D Quickly find the sum of elements between any two indices in the original array

💡 Hint

Think about how sums of subarrays can be found faster using prefix sums.

Prefix sum arrays store cumulative sums so that the sum of any subarray can be found in constant time by subtracting prefix sums.

❓ Predict Output

advanced

What is the output after updating the prefix sum array with a new element?

Given the prefix sum array [3, 7, 12, 18] for the original array, what will be the prefix sum array after adding a new element 5 to the original array and updating the prefix sums accordingly?

DSA C#

int[] prefixSum = {3, 7, 12, 18};
int newElement = 5;
int[] newPrefixSum = new int[prefixSum.Length + 1];
for (int i = 0; i < prefixSum.Length; i++) {
    newPrefixSum[i] = prefixSum[i];
}
newPrefixSum[newPrefixSum.Length - 1] = newPrefixSum[newPrefixSum.Length - 2] + newElement;
for (int i = 0; i < newPrefixSum.Length; i++) {
    Console.Write(newPrefixSum[i] + " ");
}

A 3 7 12 18 23

B 3 7 12 18 18

C 3 7 12 18 5

D 3 7 12 18 30

💡 Hint

The new prefix sum is the last prefix sum plus the new element.

The last prefix sum is 18, adding 5 gives 23 as the new last element in the prefix sum array.

🔧 Debug

advanced

What error does this prefix sum code produce?

Consider the following code snippet to create a prefix sum array. What error will it produce when run?

DSA C#

int[] arr = {1, 2, 3};
int[] prefixSum = new int[arr.Length];
for (int i = 1; i < arr.Length; i++) {
    prefixSum[i] = prefixSum[i - 1] + arr[i];
}
Console.WriteLine(string.Join(",", prefixSum));

A No error, outputs: 1,3,6

B NullReferenceException

C IndexOutOfRangeException

D SyntaxError

💡 Hint

Check the loop boundary conditions and array indexing.

The loop runs with i <= arr.Length, which tries to access prefixSum[arr.Length], an invalid index causing IndexOutOfRangeException.

🚀 Application

expert

How many subarray sums can be calculated in O(1) time using prefix sums for an array of length 5?

Using a prefix sum array, how many different subarray sums can be calculated in constant time for an array of length 5?

A 20

B 15

C 5

D 10

💡 Hint

Count all possible subarrays in an array of length n.

Number of subarrays in an array of length n is n*(n+1)/2. For n=5, it's 5*6/2=15.

Practice

1. What is the main purpose of a Prefix Sum Array in algorithms?

easy

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

B. To sort the array elements in ascending order

C. To find the maximum element in the array

D. To reverse the array elements

Solution

1. Step 1: Understand what prefix sums represent

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

2. Step 2: Identify the use of prefix sums

   Using prefix sums, we can find the sum of any subarray quickly by subtracting two prefix sums.

3. Final Answer:

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

4. Quick Check:

   Prefix Sum Array = Fast subarray sums [OK]

Hint: Prefix sums help sum subarrays fast by subtraction [OK]

Common Mistakes:

• Thinking prefix sums sort the array
• Confusing prefix sums with maximum element search
• Assuming prefix sums reverse the array

2. Which of the following C# code snippets correctly initializes a prefix sum array prefix from an integer array arr?

easy

A. int[] prefix = new int[arr.Length+1]; for(int i=1; i<=arr.Length; i++) prefix[i] = prefix[i-1] + arr[i];

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

C. int[] prefix = new int[arr.Length]; prefix[0] = arr[0]; for(int i=1; i

D. int[] prefix = new int[arr.Length]; prefix[0] = 0; for(int i=1; i

Solution

1. Step 1: Check initialization of prefix array

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

2. Step 2: Verify loop for cumulative sum

   The loop starts from 1 and adds prefix[i-1] + arr[i], correctly building prefix sums.

3. Final Answer:

   int[] prefix = new int[arr.Length]; prefix[0] = arr[0]; for(int i=1; i -> Option C

4. Quick Check:

   Correct prefix sum initialization = int[] prefix = new int[arr.Length]; prefix[0] = arr[0]; for(int i=1; i

Hint: Start prefix[0] = arr[0], then add previous prefix + current element [OK]

Common Mistakes:

• Using wrong array length for prefix
• Starting loop from 0 instead of 1
• Accessing arr out of bounds (like arr[i] when i == arr.Length)

3. Given the array arr = new int[] {2, 4, 6, 8} and its prefix sum array prefix computed as usual, what is the output of prefix[3] - prefix[1]?

medium

A. 18

B. 10

C. 12

D. 14

Solution

1. Step 1: Compute prefix sum array

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

2. Step 2: Calculate prefix[3] - prefix[1]

   20 - 6 = 14

3. Final Answer:

   14 -> Option D

4. Quick Check:

   Sum from index 2 to 3 = 6+8 = 14 [OK]

Hint: Subtract prefix sums to get subarray sum [OK]

Common Mistakes:

• Confusing indices and subtracting wrong prefix values
• Adding prefix sums instead of subtracting
• Forgetting prefix sums start at index 0

4. Consider the following code snippet to build a prefix sum array. Identify the error:

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

medium

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

B. prefix[0] should be arr[0], not 0

C. Array prefix should have length arr.Length + 1

D. No error, code is correct

Solution

1. Step 1: Check initialization of prefix[0]

   Setting prefix[0] = 0 is incorrect; it should be arr[0] to start cumulative sum correctly.

2. Step 2: Verify loop and array length

   The loop starting at 1 and array length are fine; only prefix[0] initialization is wrong.

3. Final Answer:

   prefix[0] should be arr[0], not 0 -> Option B

4. Quick Check:

   Correct prefix start = arr[0] [OK]

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

Common Mistakes:

• Starting loop at 0 causing index errors
• Using wrong prefix array size
• Assuming zero initialization is always correct

5. You have an integer array arr of length 6: {3, 1, 4, 1, 5, 9}. You want to find the sum of elements from index 2 to 5 inclusive using a prefix sum array prefix where prefix[i] stores sum of elements from index 0 to i. Which expression correctly computes this sum?

hard

A. prefix[5] - prefix[1]

B. prefix[5] - prefix[2]

C. prefix[4] - prefix[1]

D. prefix[5] + prefix[1]

Solution

1. Step 1: Understand prefix sum indexing

   prefix[i] = sum of arr[0] to arr[i]. To get sum from index 2 to 5, subtract prefix[1] (sum up to index 1) from prefix[5].

2. Step 2: Write the correct expression

   Sum = prefix[5] - prefix[1]

3. Final Answer:

   prefix[5] - prefix[1] -> Option A

4. Quick Check:

   Sum(2 to 5) = prefix[5] - prefix[1] [OK]

Hint: Sum(i to j) = prefix[j] - prefix[i-1] [OK]

Common Mistakes:

• Subtracting prefix[i] instead of prefix[i-1]
• Adding prefix sums instead of subtracting
• Using wrong indices for prefix array