Odd Number | Practice Problems

Odd Number

★★★★★

4.2

8 votes

, Basic Math, Prefix, Math, Observation, C++

Details

Submissions

Discussion

Editorial

Problem

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

Time Limit: 1

Memory Limit: 256

Source Limit:

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$ .

Contributers:

Rohit Pradhan

Shruti Sarkar