Given an integer array A of size N, and Q queries. In each query, you are given an integer X. Create a new sequence X^A[i], say sequence B. For each query find the number of even integers in the modified sequence for a given value of X.
Examples:
Input: A = {15, 6, 100, 8, 23, 45, 7, 101, 90}, N = 9, Q = 4, X = {3, 7, 10, 60}
Output: {5, 5, 4, 4}
Explanation: For first query, 3 XOR 15 = 12, 3 XOR 23 = 20, 3 XOR 45 = 46, 3 XOR 7 = 4 and 3 XOR 101 = 102. So total 5 even numbers. Similarly for the rest of the Q queries for X array.Input: A = {55, 90, 100101}, N = 3, Q = 2, X = {10006, 54401}
Output: {1, 2}
Naive Approach: To solve the problem follow the below idea:
The idea is to generate the new sequence B for each query and store it. Now, traverse through the new sequence and count the number of even numbers.
Below are the steps for the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to return the query answerint calculate(vector<int> A, int N, int X){ // Initialize even count to zero int evenCount = 0; // Traverse the given sequence for (int i : A) { // Calculate the new sequence XOR int B = i ^ X; // Ignore if the new number is odd if (B & 1) { continue; } // Increment the even count // for new even number else { evenCount++; } } // Return the even count return evenCount;}// Driver Codeint main(){ vector<int> A = { 15, 6, 100, 8, 23, 45, 7, 101, 90 }; int N = 9; int Q = 4; vector<int> X = { 3, 7, 10, 60 }; // Function Call for (int i : X) { cout << calculate(A, N, i) << " "; } return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG { // Function to return the query answer static int calculate(ArrayList<Integer> A, int N, int X) { // Initialize even count to zero int evenCount = 0; // Traverse the given sequence for (int i : A) { // Calculate the new sequence XOR int B = i ^ X; // Ignore if the new number is odd if ((B & 1) == 1) { continue; } // Increment the even count // for new even number else { evenCount++; } } // Return the even count return evenCount; } // Driver Code public static void main(String[] args) { ArrayList<Integer> A = new ArrayList<Integer>(Arrays.asList( 15, 6, 100, 8, 23, 45, 7, 101, 90)); int N = 9; int Q = 4; ArrayList<Integer> X = new ArrayList<Integer>( Arrays.asList(3, 7, 10, 60)); // Function Call for (int i : X) { System.out.print(calculate(A, N, i) + " "); } }}// This code is contributed by prasad264 |
Python3
# Function to return the query answerdef calculate(A, N, X): # Initialize even count to zero evenCount = 0 # Traverse the given sequence for i in A: # Calculate the new sequence XOR B = i ^ X # Ignore if the new number is odd if B & 1: continue # Increment the even count for new even number else: evenCount += 1 # Return the even count return evenCount# Driver Codeif __name__ == '__main__': A = [15, 6, 100, 8, 23, 45, 7, 101, 90] N = 9 Q = 4 X = [3, 7, 10, 60] # Function Call for i in X: print(calculate(A, N, i), end=" ")#contributed by tushar rokade |
C#
using System;using System.Collections.Generic;class Program{ // Function to return the query answer static int Calculate(List<int> A, int N, int X) { // Initialize even count to zero int evenCount = 0; // Traverse the given sequence foreach (int i in A) { // Calculate the new sequence XOR int B = i ^ X; // Ignore if the new number is odd if ((B & 1) != 0) { continue; } // Increment the even count // for new even number else { evenCount++; } } // Return the even count return evenCount; } // Driver Code static void Main(string[] args) { List<int> A = new List<int> { 15, 6, 100, 8, 23, 45, 7, 101, 90 }; int N = 9; //int Q = 4; List<int> X = new List<int> { 3, 7, 10, 60 }; foreach (int i in X) { Console.Write(Calculate(A, N, i) + " "); } }} |
Javascript
// JavaScript program for the above approach// Function to return the query answerfunction calculate(A, N, X) { // Initialize even count to zero let evenCount = 0; // Traverse the given sequence for (let i of A) { // Calculate the new sequence XOR let B = i ^ X; // Ignore if the new number is odd if (B & 1) { continue; } // Increment the even count // for new even number else { evenCount++; } } // Return the even count return evenCount;}// Driver Codelet A = [15, 6, 100, 8, 23, 45, 7, 101, 90];let N = 9;let Q = 4;let X = [3, 7, 10, 60];// Function Calllet output = "";for (let i of X) { output += calculate(A, N, i) + " ";}console.log(output.trim()); |
Output
5 5 4 4
Time Complexity: O(Q*N)
Auxiliary Space: O(1)
Efficient Approach: To solve the problem follow the below idea:
XOR of A and B produces a set bit when both bits are different and produces an unset bit when both bits are the same. A number can be even only if its LSB is unset. In binary representation, only the LSB contributes to the odd number addition as all other numbers are multiples of 2. Thus we have to find numbers where LSB(X) ^ LSB(A[i]) = 0 i.e. unset. It can happen only when both LSB bits are the same. Thus if the value of X is odd then odd numbers in A will produce even numbers and similarly, if the value of X is even then the even numbers will produce an even value in the new sequence.
Below are the steps for the above approach:
- Initialize a variable evenCount = 0.
- Traverse the array A[] and for each element,
- Check if it is even by doing bitwise AND with 1, increment the value of evenCount.
- Return the evenCount variable and store it in a variable evenC.
- Traverse the query array X[] and for each query,
- Check if it is odd by doing bitwise AND with 1, return the number of odd elements, N – evenC.
- Else, return evenC.
Below is the code for the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate number// of even numbersint findEven(vector<int> A, int N){ int evenCount = 0; for (int i : A) { // BITWISE AND with 1 if zero // then number is even if (!(i & 1)) { evenCount++; } } // Return the count return evenCount;}// Function to return the query answerint calculate(int evenC, int N, int X){ // If X is odd return number // of odd elements if (X & 1) { return N - evenC; } // Else X is even return number // of even elements else { return evenC; }}// Driver Codeint main(){ vector<int> A = { 15, 6, 100, 8, 23, 45, 7, 101, 90 }; int N = 9; int Q = 4; vector<int> X = { 3, 7, 10, 60 }; // Find the count of even numbers // in the given array int evenC = findEven(A, N); for (int i : X) { cout << calculate(evenC, N, i) << " "; } return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.util.ArrayList;import java.util.List;class Main { // Function to calculate number // of even numbers public static int findEven(List<Integer> A, int N) { int evenCount = 0; for (int i : A) { // BITWISE AND with 1 if zero // then number is even if (i % 2 == 0) { evenCount++; } } // Return the count return evenCount; } public static int calculate(int evenC, int N, int X) { // If X is odd return number of odd elements if (X % 2 == 1) { return N - evenC; } else { return evenC; } } // Driver Code public static void main(String[] args) { List<Integer> A = new ArrayList<>(); A.add(15); A.add(6); A.add(100); A.add(8); A.add(23); A.add(45); A.add(7); A.add(101); A.add(90); int N = 9; int Q = 4; List<Integer> X = new ArrayList<>(); X.add(3); X.add(7); X.add(10); X.add(60); // Find the count of even numbers // in the given array int evenC = findEven(A, N); for (int i : X) { System.out.print(calculate(evenC, N, i) + " "); } }} |
Python3
# python code for above approach# Function to calculate number# of even numbersdef findEven(A): evenCount = 0 for i in A: # Check if the number is even if i % 2 == 0: evenCount += 1 # Return the count return evenCount# Function to return the query answerdef calculate(evenC, N, X): # If X is odd, return number of odd elements if X % 2 != 0: return N - evenC # Else X is even, return number of even elements else: return evenC# Driver CodeA = [15, 6, 100, 8, 23, 45, 7, 101, 90]N = 9Q = 4X = [3, 7, 10, 60]# Find the count of even numbers in the given arrayevenC = findEven(A)for i in X: print(calculate(evenC, N, i), end=' ') |
C#
using System;using System.Collections.Generic;public class GFG { // Function to calculate the number // of even numbers static int FindEven(List<int> A) { int evenCount = 0; foreach(int i in A) { // BITWISE AND with 1 if zero // then number is even if ((i & 1) == 0) { evenCount++; } } // Return the count return evenCount; } // Function to return the // query answer static int Calculate(int evenC, int N, int X) { // If X is odd, return the // number of odd elements if ((X & 1) != 0) { return N - evenC; } // Else X is even, return the // number of even elements else { return evenC; } } static public void Main() { List<int> A = new List<int>{ 15, 6, 100, 8, 23, 45, 7, 101, 90 }; int N = 9; // int Q = 4; List<int> X = new List<int>{ 3, 7, 10, 60 }; // Find the count of even // numbers in the given array int evenC = FindEven(A); foreach(int i in X) { Console.Write(Calculate(evenC, N, i) + " "); } }}// This code is contributed by Prasad |
Javascript
function findEven(arr) { let evenCount = 0; for (let i of arr) { // Use the modulo operator (%) to // check if a number is even if (i % 2 === 0) { evenCount++; } } // Return the count of even numbers return evenCount;}// Function to calculate and // return the query answerfunction calculate(evenCount, N, X) { // If X is odd, return the number of odd elements if (X % 2 !== 0) { return N - evenCount; } else { // Else X is even, return the number of // even elements return evenCount; }}// Main functionfunction main() { const A = [15, 6, 100, 8, 23, 45, 7, 101, 90]; const N = 9; const Q = 4; const X = [3, 7, 10, 60]; // Find the count of even numbers in // the given array const evenC = findEven(A); const results = []; for (let i of X) { // Calculate and store the query answer results.push(calculate(evenC, N, i)); } // Print the results in the desired format console.log(results.join(' '));}// Call the main functionmain(); |
Output
5 5 4 4
Time Complexity: 
Auxiliary Space: 
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
