Odd Number

Practice

4.2 (8 votes)

Basic math

Prefix

Math

Observation

C++

Problem

46% Success 1435 Attempts 30 Points 1s Time Limit 256MB Memory 1024 KB Max Code

You are given an array \(A\) of length \(N\) and \(Q\) queries. Each query is described by two integers \(L\) and \(R\). For each query, find the number of tuples \((i, j, k)\) such that \(L \leq i \lt j \lt k \leq R\) and \(A[i] + A[j] + A[k]\) is an odd number. Input Format First line contains an integer \(T\), which denotes the number of test cases. The first line of each test case contains two integers \(N\) and \(Q\). The second line of each test case contains \(N\) space-separated integers, the elements of the array \(A\). Next \(​Q\) lines contain two space separated integers \(L\) and \(R\). Output Format For each test case, print an array of length \(Q\), \(i^{th}\) element will be the answer for the \(i^{th}\) query - the number of tuples \((i, j, k)\) such that \(L \leq i \lt j \lt k \leq R\) and \(A[i] + A[j] + A[k]\) is an odd number. Constraints \(1 \leq T \leq 10\)\(1 \leq N, Q, A[i] \leq 10^5\)\(1 \leq L \leq R \leq N\)

Sample Input

Sample Output

1 4
0 1

Explanation

For test case \(1\): First Query: \((1, 2, 3)\) is the tuple (1-based indexing) that satisfies the condition as: \(A[1] + A[2] + A[3] = 3 + 3 + 5 = 11\), which is odd. So our answer is \(1\). Second Query: \((1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)\) are the tuples (1-based indexing) that satisfy the condition as : \(A[1] + A[2] + A[3] = 3 + 3 + 5 = 11\), which is odd. \(A[1] + A[2] + A[4] = 3 + 3 + 5 = 11\), which is odd. \(A[1] + A[3] + A[4] = 3 + 5 + 5 = 13\), which is odd. \(A[2] + A[3] + A[4] = 3 + 5 + 5 = 13\), which is odd. So our answer is \(4\). For test case \(2\): First Query: There is no tuple that satisfies the condition. So our answer is \(0\). Second Query: \((3, 4, 5)\) is the tuple (1-based indexing) that satisfies the condition as: \(A[3] + A[4] + A[5] = 6 + 2 + 5 = 13\), which is odd. So our answer is \(1\).

Code Editor

You need to be logged in to access the code editor

Please wait while we load the editor

Submissions

Please login to view your submissions

You need to be logged in to access the code editor

Please wait while we load the editor