Given an array arr[] of N positive integers, the task is to answer Q queries where each query consists of a range [L, R] and you have to check whether the bitwise AND of the elements from the given index range is even or odd.
Examples:
Input: arr[] = {1, 1, 2, 3}, Q[][] = {{1, 2}, {0, 1}}
Output:
Even
Odd
(1 & 2) = 0 which is even.
(1 & 1) = 1 which is odd.Input: arr[] = {2, 1, 5, 7, 6, 8, 9}, Q[][] = {{0, 2}, {1, 2}, {2, 3}, {3, 6}}
Output:
Even
Odd
Odd
Even
Approach:
- The bitwise AND in an index range [L, R] will be odd if all the elements in that index range is odd otherwise, it will be even.
- So, check whether all the elements in the index range [L, R] is odd or not.
- In order to answer each query optimally, create an array and mark the positions where the value is odd and then take the prefix sum of this array.
- Now, the count of odd numbers in the index range [L, R] can be calculated as pre[R] – pre[L – 1].
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;const int MAXN = 1000005;int even[MAXN], odd[MAXN];// Function to precompute the count// of even and odd numbersvoid precompute(int arr[], int n){ for (int i = 0; i < n; i++) { // If the current element is odd // then put 1 at odd[i] if (arr[i] % 2 == 1) odd[i] = 1; // If the current element is even // then put 1 at even[i] if (arr[i] % 2 == 0) even[i] = 1; } // Taking the prefix sums of these two arrays // so we can get the count of even and odd // numbers in a range [L, R] in O(1) for (int i = 1; i < n; i++) { even[i] = even[i] + even[i - 1]; odd[i] = odd[i] + odd[i - 1]; }}// Function that returns true if the bitwise// AND of the subarray a[L...R] is oddbool isOdd(int L, int R){ // cnt will store the count of odd // numbers in the range [L, R] int cnt = odd[R]; if (L > 0) cnt -= odd[L - 1]; // Check if all the numbers in // the range are odd or not if (cnt == R - L + 1) return true; return false;}// Function to perform the queriesvoid performQueries(int a[], int n, int q[][2], int m){ precompute(a, n); // Perform queries for (int i = 0; i < m; i++) { int L = q[i][0], R = q[i][1]; if (isOdd(L, R)) cout << "Odd\n"; else cout << "Even\n"; }}// Driver codeint main(){ int a[] = { 2, 1, 5, 7, 6, 8, 9 }; int n = sizeof(a) / sizeof(a[0]); // Queries int q[][2] = { { 0, 2 }, { 1, 2 }, { 2, 3 }, { 3, 6 } }; int m = sizeof(q) / sizeof(q[0]); performQueries(a, n, q, m); return 0;} |
Java
// Java implementation of the approachclass GFG { static final int MAXN = 1000005; static int even[] = new int[MAXN]; static int odd[] = new int[MAXN]; // Function to precompute the count // of even and odd numbers static void precompute(int arr[], int n) { for (int i = 0; i < n; i++) { // If the current element is odd // then put 1 at odd[i] if (arr[i] % 2 == 1) odd[i] = 1; // If the current element is even // then put 1 at even[i] if (arr[i] % 2 == 0) even[i] = 1; } // Taking the prefix sums of these two arrays // so we can get the count of even and odd // numbers in a range [L, R] in O(1) for (int i = 1; i < n; i++) { even[i] = even[i] + even[i - 1]; odd[i] = odd[i] + odd[i - 1]; } } // Function that returns true if the bitwise // AND of the subarray a[L...R] is odd static boolean isOdd(int L, int R) { // cnt will store the count of odd // numbers in the range [L, R] int cnt = odd[R]; if (L > 0) cnt -= odd[L - 1]; // Check if all the numbers in // the range are odd or not if (cnt == R - L + 1) return true; return false; } // Function to perform the queries static void performQueries(int a[], int n, int q[][], int m) { precompute(a, n); // Perform queries for (int i = 0; i < m; i++) { int L = q[i][0], R = q[i][1]; if (isOdd(L, R)) System.out.println("Odd"); else System.out.println("Even"); } } // Driver code public static void main(String args[]) { int[] a = { 2, 1, 5, 7, 6, 8, 9 }; int n = a.length; // Queries int q[][] = { { 0, 2 }, { 1, 2 }, { 2, 3 }, { 3, 6 } }; int m = q.length; performQueries(a, n, q, m); }}// This code is contributed by AnkitRai01 |
Python3
# Python implementation of the approachMAXN = 1000005even = [0] * MAXNodd = [0] * MAXN# Function to precompute the count# of even and odd numbersdef precompute(arr, n): for i in range(n): # If the current element is odd # then put 1 at odd[i] if (arr[i] % 2 == 1): odd[i] = 1 # If the current element is even # then put 1 at even[i] if (arr[i] % 2 == 0): even[i] = 1 # Taking the prefix sums of these two arrays # so we can get the count of even and odd # numbers in a range [L, R] in O(1) for i in range(1, n): even[i] = even[i] + even[i - 1] odd[i] = odd[i] + odd[i - 1]# Function that returns True if the bitwise# AND of the subarray a[L...R] is odddef isOdd(L, R): # cnt will store the count of odd # numbers in the range [L, R] cnt = odd[R] if (L > 0): cnt -= odd[L - 1] # Check if all the numbers in # the range are odd or not if (cnt == R - L + 1): return True return False# Function to perform the queriesdef performQueries(a, n, q, m): precompute(a, n) # Perform queries for i in range(m): L = q[i][0] R = q[i][1] if (isOdd(L, R)): print("Odd") else: print("Even")# Driver codeif __name__ == '__main__': a = [2, 1, 5, 7, 6, 8, 9] n = len(a) # Queries q = [[0, 2], [1, 2], [2, 3], [3, 6]] m = len(q) performQueries(a, n, q, m)# This code is contributed by PrinciRaj1992 |
C#
// C# implementation of the approachusing System;class GFG { static readonly int MAXN = 1000005; static int[] even = new int[MAXN]; static int[] odd = new int[MAXN]; // Function to precompute the count // of even and odd numbers static void precompute(int[] arr, int n) { for (int i = 0; i < n; i++) { // If the current element is odd // then put 1 at odd[i] if (arr[i] % 2 == 1) odd[i] = 1; // If the current element is even // then put 1 at even[i] if (arr[i] % 2 == 0) even[i] = 1; } // Taking the prefix sums of these two arrays // so we can get the count of even and odd // numbers in a range [L, R] in O(1) for (int i = 1; i < n; i++) { even[i] = even[i] + even[i - 1]; odd[i] = odd[i] + odd[i - 1]; } } // Function that returns true if the bitwise // AND of the subarray a[L...R] is odd static bool isOdd(int L, int R) { // cnt will store the count of odd // numbers in the range [L, R] int cnt = odd[R]; if (L > 0) cnt -= odd[L - 1]; // Check if all the numbers in // the range are odd or not if (cnt == R - L + 1) return true; return false; } // Function to perform the queries static void performQueries(int[] a, int n, int[, ] q, int m) { precompute(a, n); // Perform queries for (int i = 0; i < m; i++) { int L = q[i, 0], R = q[i, 1]; if (isOdd(L, R)) Console.WriteLine("Odd"); else Console.WriteLine("Even"); } } // Driver code public static void Main(String[] args) { int[] a = { 2, 1, 5, 7, 6, 8, 9 }; int n = a.Length; // Queries int[, ] q = { { 0, 2 }, { 1, 2 }, { 2, 3 }, { 3, 6 } }; int m = q.GetLength(0); performQueries(a, n, q, m); }}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript implementation of the approachvar MAXN = 1000005;var even = Array(MAXN).fill(0);var odd = Array(MAXN).fill(0);// Function to precompute the count// of even and odd numbersfunction precompute(arr, n){ for (var i = 0; i < n; i++) { // If the current element is odd // then put 1 at odd[i] if (arr[i] % 2 == 1) odd[i] = 1; // If the current element is even // then put 1 at even[i] if (arr[i] % 2 == 0) even[i] = 1; } // Taking the prefix sums of these two arrays // so we can get the count of even and odd // numbers in a range [L, R] in O(1) for (var i = 1; i < n; i++) { even[i] = even[i] + even[i - 1]; odd[i] = odd[i] + odd[i - 1]; }}// Function that returns true if the bitwise// AND of the subarray a[L...R] is oddfunction isOdd(L, R){ // cnt will store the count of odd // numbers in the range [L, R] var cnt = odd[R]; if (L > 0) cnt -= odd[L - 1]; // Check if all the numbers in // the range are odd or not if (cnt == R - L + 1) return true; return false;}// Function to perform the queriesfunction performQueries(a, n, q, m){ precompute(a, n); // Perform queries for (var i = 0; i < m; i++) { var L = q[i][0], R = q[i][1]; if (isOdd(L, R)) document.write( "Odd"+"<br>"); else document.write("Even"+"<br>"); }}// Driver codevar a = [2, 1, 5, 7, 6, 8, 9];var n = a.length;// Queriesvar q = [ [ 0, 2 ], [ 1, 2 ], [ 2, 3 ], [ 3, 6 ] ];var m = q.length;performQueries(a, n, q, m);// This code is contributed by itsok.</script> |
Output:
Even Odd Odd Even
Time Complexity: O(Q) where Q is the number of queries.
Auxiliary Space: O(MAXN)
Share your thoughts in the comments
