Prefix Sum - Find number of Event number count - Leetcode

Given an array of size N and Q queries, where each query is represented as a pair (s, e), the task is to determine the number of even elements within the specified index range from s to e for each query.

Specifically, for each query, we need to count how many elements in the array between the start index s and the end index e (inclusive) are even numbers. This involves iterating through the array segment defined by the indices s and e and checking each element to see if it is divisible by 2, thereby determining if it is even. The result for each query should be the total count of such even elements within the given range.

Problem Constraints

1 <= N <= 10⁵
1 <= Q <= 10⁵
1 <= A[i] <= 100
0 <= B[i][0] <= B[i][1] < N

Input Format

First argument A is an array of integers.
Second argument B is a 2D array of integers.

Output Format

Return an array of integers.

Example Input

Input 1:
A = [1, 2, 3, 4, 5]
B = [   [0,2] 
        [1,4]   ]

Input 2:
A = [2, 1, 8, 3, 9]
B = [   [0,3] 
        [2,4]   ]

Example Output

Output 1: [1, 2]
Output 2: [10, 17]

Example Explanation

For input 1:
The subarray for the first query is [1, 2, 3] whose count of even indices is 1.
The subarray for the second query is [2, 3, 4, 5] whose count of even indices is 2.

For input 2:
The subarray for the first query is [2, 1, 8, 3] whose count of even indices is 2.
The subarray for the second query is [8, 3, 9] whose count of even indices is 1.

public class SumOfEvenIndices {

    public static int[] evenCount(int[] A, int[][] B) {
        int result[] = new int[A.length];
        int prefixSum = 0;
        // Create Prefix Sum array
        for (int i = 0; i < A.length; i++) {
            if (A[i] % 2 == 0) { // Treat as event number and make sum as 1.
                prefixSum = 1 + prefixSum;
                result[i] = prefixSum;

            } else {
                result[i] = prefixSum;
            }

        }

        int output[] = new int[B.length];

        for (int j = 0; j < B.length; j++) {
            int startIndex = B[j][0];
            int endIndex = B[j][1];
            if (startIndex == 0) {

                output[j] = result[endIndex];
            } else {

                output[j] = result[endIndex] - result[startIndex - 1];
            }

        }

        return output;
    }
}

This Java code defines a class SumOfEvenIndices with a method evenCount that calculates the count of even numbers in specified ranges of an array. The code uses a prefix sum-like technique to efficiently determine the number of even elements within these ranges.

Code Breakdown and Explanation

public class SumOfEvenIndices {
    public static int[] evenCount(int[] A, int[][] B) {
        int result[] = new int[A.length];
        int prefixSum = 0;

• evenCount Method:

  • Takes two arguments:

    • int[] A: The input array containing integers.

    • int[][] B: A 2D array where each row represents a range [startIndex, endIndex].

  • Output: An integer array where each element represents the count of even numbers in the corresponding range specified in B.

  • Variables:

    • result[]: This array will store the cumulative count of even numbers up to each index in A.

    • prefixSum: A running sum used to keep track of the number of even elements encountered so far.

1. Constructing the Even Prefix Sum Array:

for (int i = 0; i < A.length; i++) {
            if (A[i] % 2 == 0) { // Treat as even number and make sum as 1.
                prefixSum = 1 + prefixSum;
                result[i] = prefixSum;
            } else {
                result[i] = prefixSum;
            }
        }

• for loop: Iterates over the array A.

  • Condition if (A[i] % 2 == 0):

    • Checks if the element A[i] is even. If it is, the prefixSum is incremented by 1, indicating one more even number has been encountered.

    • result[i] = prefixSum;: Stores the updated count of even numbers up to index i.

  • else block:

    • If A[i] is odd, prefixSum remains unchanged, and result[i] is set to the current prefixSum.

• result[] array: By the end of this loop, result[i] contains the count of even numbers from the start of the array up to index i.

2. Processing Range Queries:

int output[] = new int[B.length];

        for (int j = 0; j < B.length; j++) {
            int startIndex = B[j][0];
            int endIndex = B[j][1];
            if (startIndex == 0) {
                output[j] = result[endIndex];
            } else {
                output[j] = result[endIndex] - result[startIndex - 1];
            }
        }

        return output;
    }
}

• output[]: This array will store the count of even numbers for each range specified in B.

• for loop: Iterates over the 2D array B to process each range [startIndex, endIndex].

  • Extract startIndex and endIndex:

    • For each query j, startIndex = B[j][0] and endIndex = B[j][1] represent the start and end indices of the current range.

  • Condition if (startIndex == 0):

    • If the startIndex is 0, the count of even numbers from the start of the array to endIndex is simply result[endIndex].

  • else block:

    • If startIndex is not 0, the count of even numbers between startIndex and endIndex is calculated by subtracting result[startIndex - 1] from result[endIndex]. This operation effectively removes the count of even numbers before startIndex.

• Return Statement:

  • The method returns the output[] array, which contains the count of even numbers for each range in B.

Summary:

• Prefix Sum Array (result[]):

  • The array result[] is used to store the cumulative count of even numbers up to each index in A.

• Range Query Calculation:

  • For each range [startIndex, endIndex], the number of even numbers in that range is efficiently calculated using the result[] array.

• Efficiency:

  • This approach allows for efficient querying of the count of even numbers in any given range after an initial O(n) preprocessing step, making the range queries O(1) for each query.

This method is particularly useful when you have multiple range queries on the same array, as it reduces the time complexity of each query to constant time.

This article introduces a Java solution to efficiently count even numbers within specified index ranges of an array given multiple queries. By leveraging a prefix sum technique, we preprocess the array to create a cumulative count of even numbers up to each index, allowing for constant time query handling. This method ensures efficient range queries after an initial preprocessing step, making it suitable for large datasets with numerous queries.