Count Even Or Odd
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.
CodingNinjas
author
2y
One simple solution is to find the remainder after dividing by 2.
A better solution is to use bitwise operators. We need to check whether last bit is 1 or not. If last bit is 1 then number is odd, othe...read more
CodingNinjas
author
2y
Brute Force
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 t...read more
CodingNinjas
author
2y
Segment Tree
Java (SE 1.8)
C++ (g++ 5.4)
Python (3.5)
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)
O(N) where ‘N’ is the size of the array.
We are creating an array of size 4* N + 1 . Thus space complexity will be O(N).
Time Complexity: O(nlogn)Explanation:O(N*log(N) + Q*log(N) ) where ‘N’ is the size of the array and ‘Q’ is the number of queries.
We have to build a segment tree that takes N*log(N) and we have to process ‘Q’ queries and each query takes log(N) time with the segment tree.
Java (SE 1.8)
/*
Time Complexity : O(N*log(N) + Q*log(N))
Space Complexity : O(N)
Where N is size of array and Q is number of queries.
*/
import java.util.List;
import java.util.ArrayList;
public class Solution {
static int[] segment;
public static void buildTree(int[] arr, int l, int r, int index) {
if (l > r) {
return;
}
// It means it has only one element
if (l == r) {
int temp = 0;
if (arr[l] % 2 == 0) {
temp = 1;
}
segment[index] = temp;
return;
}
int mid = (l + r) / 2;
int lChild = 2 * index + 1;
int rChild = 2 * index + 2;
buildTree(arr, l, mid, lChild);
buildTree(arr, mid + 1, r, rChild);
// Merging ans from leftChild and rightChild.
segment[index] = segment[lChild] + segment[rChild];
}
public static int query(int l, int r, int ql, int qr, int index) {
// If the l and r lies inside queries range then that complete node is part of
// ans.
if (ql <= l && qr >= r) {
return segment[index];
}
int mid = (l + r) / 2;
// If the leftChild has no overlapping with queries range then ans only lies in
// right part.
if (mid < ql) {
return query(mid + 1, r, ql, qr, 2 * index + 2);
}
// If the rightChild has no overlapping with queries range then ans only lies in
// left part.
if (mid + 1 > qr) {
return query(l, mid, ql, qr, 2 * index + 1);
}
int ans1 = query(l, mid, ql, qr, 2 * index + 1);
int ans2 = query(mid + 1, r, ql, qr, 2 * index + 2);
// Merging answer from left and right child.
return ans1 + ans2;
}
public static void update(int l, int r, int i, int element, int index) {
if (l > r || i < l || i > r) {
return;
}
if (l == r) {
segment[index] = element;
return;
}
int mid = (l + r) >> 1;
int lChild = 2 * index + 1;
int rChild = 2 * index + 2;
update(l, mid, i, element, lChild);
update(mid + 1, r, i, element, rChild);
// Merging ans from leftChild and rightChild.
segment[index] = segment[lChild] + segment[rChild];
}
public static List solve(int N, int[] arr, int q, int[][] queries) {
segment=new int[4 * N + 1];
buildTree(arr, 0, N - 1, 0);
List ans1 = new ArrayList();
for (int i = 0; i < q; i++) {
if (queries[i][0] == 0) {
int temp = 0;
if (queries[i][2] % 2 == 0) {
temp = 1;
}
int l = temp;
update(0, N - 1, queries[i][1], l, 0);
} else {
int ans = query(0, N - 1, queries[i][1], queries[i][2], 0);
// Counting the answer for odd.
if (queries[i][0] == 2) {
ans = queries[i][2] - queries[i][1] + 1 - ans;
}
ans1.add(ans);
}
}
return ans1;
}
} C++ (g++ 5.4)
/*
Time Complexity : O(N*log(N) + Q*log(N))
Space Complexity : O(N)
Where N is size of array and Q is number of queries.
*/
class segmentTree
{
public:
vector segment;
segmentTree(int N)
{
// Creating a segment tree of size 4*N+1.
segment = vector(4 * N + 1);
}
void buildTree(vector &arr, int l, int r, int index = 0)
{
if (l > r)
{
return;
}
// It means it has only one element
if (l == r)
{
segment[index] = (arr[l] % 2 == 0);
return;
}
int mid = (l + r) / 2;
int lChild = 2 * index + 1;
int rChild = 2 * index + 2;
buildTree(arr, l, mid, lChild);
buildTree(arr, mid + 1, r, rChild);
// Merging ans from leftChild and rightChild.
segment[index] = segment[lChild] + segment[rChild];
}
int query(int l, int r, int ql, int qr, int index = 0)
{
// If the l and r lies inside queries range then that complete node is part of ans.
if (ql <= l && qr >= r)
{
return segment[index];
}
int mid = (l + r) / 2;
// If the leftChild has no overlapping with queries range then ans only lies in right part.
if (mid < ql)
{
return query(mid + 1, r, ql, qr, 2 * index + 2);
}
// If the rightChild has no overlapping with queries range then ans only lies in left part.
if (mid + 1 > qr)
{
return query(l, mid, ql, qr, 2 * index + 1);
}
int ans1 = query(l, mid, ql, qr, 2 * index + 1);
int ans2 = query(mid + 1, r, ql, qr, 2 * index + 2);
// Merging answer from left and right child.
return ans1 + ans2;
}
void update(int l, int r, int i, int element, int index = 0)
{
if (l > r || i < l || i > r)
{
return;
}
if (l == r)
{
segment[index] = element;
return;
}
int mid = (l + r) >> 1;
int lChild = 2 * index + 1;
int rChild = 2 * index + 2;
update(l, mid, i, element, lChild);
update(mid + 1, r, i, element, rChild);
// Merging ans from leftChild and rightChild.
segment[index] = segment[lChild] + segment[rChild];
}
};
vector solve(int N, vector &arr, int q, vector> &queries)
{
segmentTree tree(N);
// Building tree corresponding to array.
tree.buildTree(arr, 0, N - 1);
vector ans1;
for (int i = 0; i < q; i++)
{
if (queries[i][0] == 0)
{
int l = (queries[i][2] % 2 == 0);
tree.update(0, N - 1, queries[i][1], l);
}
else
{
int ans = tree.query(0, N - 1, queries[i][1], queries[i][2]);
// Counting the answer for odd.
if (queries[i][0] == 2)
{
ans = queries[i][2] - queries[i][1] + 1 - ans;
}
ans1.push_back(ans);
}
}
return ans1;
} Python (3.5)
"""
Time Complexity : O(N*log(N) + Q*log(N))
Space Complexity : O(N)
Where N is size of array and Q is number of queries.
"""
class segmentTree:
segment = list()
def __init__(self, N):
# Creating a segment tree of size 4*N+1.
self.segment = [0] * (4 * N + 1)
def buildTree(self, arr, l, r, index=0):
if l > r:
return
# It means it has only one element
if l == r:
self.segment[index] = arr[l] % 2 == 0
return
mid = (l + r) // 2
lChild = 2 * index + 1
rChild = 2 * index + 2
self.buildTree(arr, l, mid, lChild)
self.buildTree(arr, mid + 1, r, rChild)
# Merging ans from leftChild and rightChild.
self.segment[index] = self.segment[lChild] + self.segment[rChild]
def query(self, l, r, ql, qr, index=0):
# If the l and r lies inside queries range then that complete node is part of ans.
if ql <= l and qr >= r:
return self.segment[index]
mid = (l + r) // 2
# If the leftChild has no overlapping with queries range then ans only lies in right part.
if mid < ql:
return self.query(mid + 1, r, ql, qr, 2 * index + 2)
# If the rightChild has no overlapping with queries range then ans only lies in left part.
if mid + 1 > qr:
return self.query(l, mid, ql, qr, 2 * index + 1)
ans1 = self.query(l, mid, ql, qr, 2 * index + 1)
ans2 = self.query(mid + 1, r, ql, qr, 2 * index + 2)
# Merging answer from left and right child.
return ans1 + ans2
def update(self, l, r, i, element, index=0):
if l > r or i < l or i > r:
return
if l == r:
self.segment[index] = element
return
mid = (l + r) >> 1
lChild = 2 * index + 1
rChild = 2 * index + 2
self.update(l, mid, i, element, lChild)
self.update(mid + 1, r, i, element, rChild)
# Merging ans from leftChild and rightChild.
self.segment[index] = self.segment[lChild] + self.segment[rChild]
def solve(N, arr, q, queries):
tree = segmentTree(N)
# Building tree corresponding to array.
tree.buildTree(arr, 0, N - 1)
ans1 = []
for i in range(q):
if queries[i][0] == 0:
l = queries[i][2] % 2 == 0
tree.update(0, N - 1, queries[i][1], l)
else:
ans = tree.query(0, N - 1, queries[i][1], queries[i][2])
# Counting the answer for odd.
if queries[i][0] == 2:
ans = queries[i][2] - queries[i][1] + 1 - ans
ans1.append(int(ans))
return ans1
CodingNinjas
author
2y
Fenwick Tree
Python (3.5)
Java (SE 1.8)
C++ (g++ 5.4)
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.
O(N) where ‘N’ is the size of the array
We are creating an array of size N. Thus space complexity will be O(N).
Time Complexity: O(nlogn)Explanation:O(N * log(N) + Q*log(N) ) where ‘N’ is the size of the array and ‘Q’ is the number of queries.
We have to build a Fenwick tree that takes N*log(N) and we have to process Q queries and each query takes log(N) time with the segment tree.
Python (3.5)
"""
Time Complexity : O(N*log(N) + Q*log(N))
Space Complexity : O(N)
Where N is size of array and Q is number of queries.
"""
class fenwickTree:
fenwick = list()
def __init__(self, N):
self.fenwick = [0] * (N + 2)
def query(self, l):
l += 1
ans = 0
while l > 0:
ans += self.fenwick[l]
l -= l & (-l)
return ans
def update(self, i, element, N):
i += 1
while i <= N:
self.fenwick[i] += element
i += i & (-i)
def solve(N, arr, q, queries):
tree = fenwickTree(N)
# Updating Fenwick tree corresponding to array.
ans1 = list()
for i in range(N):
tree.update(i, (arr[i] % 2) == 0, N)
for i in range(q):
if queries[i][0] == 0:
# Updating in tree.
tree.update(queries[i][1], queries[i][2] % 2 == 0, N)
x = arr[queries[i][1]] % 2 == 0
if x == 1:
x = -1
tree.update(queries[i][1], x, N)
arr[queries[i][1]] = queries[i][2]
else:
ans = tree.query(queries[i][2]) - tree.query(queries[i][1] - 1)
# If odd then it will total - even .
if queries[i][0] == 2:
ans = queries[i][2] - queries[i][1] + 1 - ans
ans1.append(ans)
return ans1
Java (SE 1.8)
/*
Time Complexity : O(N*log(N) + Q*log(N))
Space Complexity : O(N)
Where N is size of array and Q is number of queries.
*/
import java.util.List;
import java.util.ArrayList;
public class Solution {
static int[] fenwick;
public static int query(int l) {
l++;
int ans = 0;
while (l > 0) {
ans += fenwick[l];
l -= (l & (-l));
}
return ans;
}
public static void update(int i, int element, int N) {
i++;
while (i <= N) {
fenwick[i] += element;
i += (i & (-i));
}
}
public static List solve(int N, int[] arr, int q, int[][] queries) {
fenwick = new int[N + 2];
List ans1 = new ArrayList();
for (int i = 0; i < N; i++) {
int temp = 0;
if (arr[i] % 2 == 0) {
temp = 1;
}
update(i, temp, N);
}
for (int i = 0; i < q; i++) {
if (queries[i][0] == 0) {
// Updating in tree.
int temp = 0;
if (queries[i][2] % 2 == 0) {
temp = 1;
}
update(queries[i][1], temp, N);
temp = (arr[queries[i][1]] & 1);
if (temp == 0) {
temp = -1;
} else {
temp = 0;
}
update(queries[i][1], temp, N);
arr[queries[i][1]] = queries[i][2];
} else {
int ans = query(queries[i][2]) - query(queries[i][1] - 1);
// If odd then it will total - even .
if (queries[i][0] == 2) {
ans = queries[i][2] - queries[i][1] + 1 - ans;
}
ans1.add(ans);
}
}
return ans1;
}
} C++ (g++ 5.4)
/*
Time Complexity : O(N*log(N) + Q*log(N))
Space Complexity : O(N)
Where N is size of array and Q is number of queries.
*/
class fenwickTree {
public:
vectorfenwick;
fenwickTree(int N)
{
fenwick = vector(N + 2, 0);
}
int query(int l)
{
l++;
int ans = 0;
while (l > 0)
{
ans += fenwick[l];
l -= (l & (-l));
}
return ans;
}
void update(int i, int element, int N)
{
i++;
while (i <= N)
{
fenwick[i] += element;
i += (i & (-i));
}
}
};
vector solve(int N, vector &arr, int q, vector> &queries)
{
fenwickTree tree(N);
// Updating Fenwick tree corresponding to array.
vectorans1;
for (int i = 0; i < N; i++)
{
tree.update(i, (arr[i] % 2) == 0, N);
}
for (int i = 0; i < q; i++)
{
if (queries[i][0] == 0)
{ // Updating in tree.
tree.update(queries[i][1], queries[i][2] % 2 == 0, N);
int x = (arr[queries[i][1]] % 2 == 0);
if (x == 1)
{
x = -1;
}
tree.update(queries[i][1], x, N);
arr[queries[i][1]] = queries[i][2];
}
else
{
int ans = tree.query(queries[i][2]) - tree.query(queries[i][1] - 1);
// If odd then it will total - even .
if (queries[i][0] == 2)
{
ans = queries[i][2] - queries[i][1] + 1 - ans;
}
ans1.push_back(ans);
}
}
return ans1;
}
Add answer anonymously...
Top LTIMindtree Software Developer interview questions & answers
Popular interview questions of Software Developer
Top HR questions asked in LTIMindtree Software Developer
Stay ahead in your career. Get AmbitionBox app
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+
Reviews
4 L+
Interviews
4 Cr+
Salaries
1 Cr+
Users/Month
Contribute to help millions
Get AmbitionBox app
Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.
Follow us
