Last Updated: 27 Apr, 2021

Count Even Or Odd

Hard

Asked in companies

Solve now

Problem statement

Tanmay and Rohit are best buddies. One day Tanmay gives Rohit a problem to test his intelligence and skills. He gives him an array of N natural numbers and asks him to solve the following queries:-

Query 0 :

0 x y

This operation modifies the element present at index x to y.

Query 1 :

1 x y

This operation counts the number of even numbers in range x to y inclusive.

Query 2 :

2 x y

This operation counts the number of odd numbers in range x to y inclusive.

Input Format :

The first line of the test case contains a single integer ‘N’  denoting the size of the ‘arr’ array.

The second line of each test case contains ‘N’ space-separated integers denoting the elements array  ‘arr’.

The third line of each test case contains an integer ‘q’ denoting the number of queries.

The next ‘q’  lines of each test case contain 3  space-separated integers denoting the following:
0 x y - modify the number at index x to y. 
1 x y - count the number of even numbers in range x to y inclusive.
2 x y - count the number of odd numbers in range x to y inclusive.

Output Format :

For each query, print an integer denoting the answer.

The output of each query will be printed in a separate line.

Constraints :

1 <= N, Q <= 10^5
0 <= l <=  r  <= N - 1 
0 <= arr[i] <= 10 ^ 9
1 <= x <= N
0 <= y <= 10 ^ 9

Where 'arr[i]' denotes the 'ith' element of arr.

Time limit: 1 sec

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Solve now

Approaches

01 Approach

The key idea is to process the queries as asked.

For query of type 0 simply just update arr[i] to x.
For query of type 1 simply run a loop from ‘l’ to ‘r’ and count the number of elements that are even.
For query of type 2 simply run a loop from ‘l’ to ‘r’ and count the number of elements that are even.

Solve now

02 Approach

The main idea is to process the queries efficiently we will use a segment tree. To know more about segment tree refer to this:- https://cp-algorithms.com/data_structures/segment_tree.html

At each node in the segment tree, we will store a number of elements that are even which are within the range of the segment. In the build function of the segment tree, the number of elements which are even corresponding to the parent node will be the sum of left and right child nodes.

segment[parent] = segment[leftChild] + segment[rightChild]

Using the value stored in the segment we can the answer for query of type 1 and type 2. As if the number of elements in the segment is N and the number of even elements is l then the number of odd elements will be N - l.
In the query function of the segment tree, we will recursively calculate the answer for the left and right part and simply return their sum.
In update we will store 1 or 0 in the node corresponding to i. Such that segment[index] = (x%2==0)

Solve now

03 Approach

The main idea is to process the queries efficiently we will use the Fenwick tree. To know more about the Fenwick tree refer to this https://cp-algorithms.com/data_structures/fenwick.html

For building the Fenwick tree we will simply update arr[i] at the ith index in Fenwick tree .For this we will pass 1 if arr[i] is even else 0 in update function of Fenwick tree.
The query function of the Fenwick function will simply return the number of even elements from 1 to ‘r’.So the number of even elements from l tor is the query(r) - query(l-1). Similarly the number of odd elements will be the Number of elements in the segment - The number of even elements.
For updating, we will simply pass 1 if the given element is even else we will pass 0.

Solve now