Given two arrays, arr[] and brr[] of size N and M respectively, the task is to find the count of pairs (arr[i], brr[j]) such that the product of elements of the pairs is an even number.
Examples:
Input: arr[] = { 1, 2, 3 }, brr[] = { 1, 2 }
Output: 4
Explanation:
Pairs with even product are: { (arr[0], brr[1]), (arr[1], brr[0]), (arr[1], brr[1]), (arr[2], brr[1]) }.
Therefore, the required output is 4.Input: arr[] = { 3, 2, 1, 4, 4}, brr[] = { 1, 4, 2, 3, 1 }
Output: 19
Brute Force Approach:
The brute force approach to solve this problem is to use nested loops to iterate through all possible pairs of elements in the two arrays and check if the product of the pair is even. If the product is even, increment the count of such pairs.
The steps involved in the brute force approach are:
- Initialize a variable count to 0 to keep track of the count of pairs with even product.
- Use a nested loop to iterate through all possible pairs of elements in the two arrays.
- Check if the product of the pair is even using the modulo operator (%). If the product is even, increment the count variable.
- After all pairs have been checked, return the count variable as the output.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;int countPairs(int arr[], int n, int brr[], int m) { int count = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if ((arr[i] * brr[j]) % 2 == 0) count++; } } return count;}int main() { int arr[] = {1, 2, 3}; int brr[] = {1, 2}; int n = sizeof(arr) / sizeof(arr[0]); int m = sizeof(brr) / sizeof(brr[0]); cout << countPairs(arr, n, brr, m) << endl; return 0;} |
Java
import java.util.*;class Main { public static int countPairs(int[] arr, int n, int[] brr, int m) { int count = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if ((arr[i] * brr[j]) % 2 == 0) count++; } } return count; } public static void main(String[] args) { int[] arr = {1, 2, 3}; int[] brr = {1, 2}; int n = arr.length; int m = brr.length; System.out.println(countPairs(arr, n, brr, m)); }} |
Python3
# This function takes two arrays of integers and their sizes as inputdef count_pairs(arr, n, brr, m): count = 0 # Traverse both arrays and check if the product of the current elements # is even, increment count if true for i in range(n): for j in range(m): if (arr[i] * brr[j]) % 2 == 0: count += 1 return count# Driver programarr = [1, 2, 3]brr = [1, 2]n = len(arr)m = len(brr)print(count_pairs(arr, n, brr, m)) |
C#
using System;class Program{ static int CountPairs(int[] arr, int n, int[] brr, int m) { int count = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if ((arr[i] * brr[j]) % 2 == 0) { count++; } } } return count; } static void Main(string[] args) { int[] arr = { 1, 2, 3 }; int[] brr = { 1, 2 }; int n = arr.Length; int m = brr.Length; Console.WriteLine(CountPairs(arr, n, brr, m)); }}// This code is contributed by Prajwal Kandekar |
Javascript
// Function to count pairs from two arrays where the product is evenfunction countPairs(arr, brr) { let count = 0; // Iterate through the first array for (let i = 0; i < arr.length; i++) { // Iterate through the second array for (let j = 0; j < brr.length; j++) { // Check if the product of elements from both arrays is even if ((arr[i] * brr[j]) % 2 === 0) { count++; } } } return count;}// Main functionfunction main() { const arr = [1, 2, 3]; const brr = [1, 2]; // Call the countPairs function and display the result const result = countPairs(arr, brr); console.log(result);}// Call the main functionmain(); |
Output
4
Time Complexity: O(N*M)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized based on the following properties of product of two numbers:
Odd * Odd = Odd
Even * Odd = Even
Even * Even = Even
Follow the steps below to solve the problem:
- Initialize two variables, say cntOddArr and cntOddBrr, to store the count of odd numbers present in the arrays arr[] and brr[] respectively.
- Traverse the array arr[] and for every array element, check if it is an odd number or not. If found to be true, then update cntOddArr += 1.
- Traverse the array brr[] and for every array element, index, check if it is an odd number or not. If found to be true, then update cntOddBrr += 1.
- Finally, print the value of ((N * M) – cntOddArr * cntOddBrr).
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to count pairs (arr[i], brr[j])// whose product is an even numberint cntPairsInTwoArray(int arr[], int brr[], int N, int M){ // Stores count of odd // numbers in arr[] int cntOddArr = 0; // Stores count of odd // numbers in brr[] int cntOddBrr = 0; // Traverse the array, arr[] for (int i = 0; i < N; i++) { // If arr[i] is // an odd number if (arr[i] & 1) { // Update cntOddArr cntOddArr += 1; } } // Traverse the array, brr[] for (int i = 0; i < M; i++) { // If brr[i] is // an odd number if (brr[i] & 1) { // Update cntOddArr cntOddBrr += 1; } } // Return pairs whose product // is an even number return (N * M) - (cntOddArr * cntOddBrr);}// Driver Codeint main(){ int arr[] = { 1, 2, 3 }; int N = sizeof(arr) / sizeof(arr[0]); int brr[] = { 1, 2 }; int M = sizeof(brr) / sizeof(brr[0]); cout << cntPairsInTwoArray(arr, brr, N, M); return 0;} |
Java
// Java program to implement// the above approachimport java.util.*;class GFG{// Function to count pairs (arr[i], brr[j])// whose product is an even numberstatic int cntPairsInTwoArray(int arr[], int brr[], int N, int M){ // Stores count of odd // numbers in arr[] int cntOddArr = 0; // Stores count of odd // numbers in brr[] int cntOddBrr = 0; // Traverse the array, arr[] for (int i = 0; i < N; i++) { // If arr[i] is // an odd number if (arr[i] % 2 == 1) { // Update cntOddArr cntOddArr += 1; } } // Traverse the array, brr[] for (int i = 0; i < M; i++) { // If brr[i] is // an odd number if (brr[i] % 2 == 1) { // Update cntOddArr cntOddBrr += 1; } } // Return pairs whose product // is an even number return (N * M) - (cntOddArr * cntOddBrr);}// Driver Codepublic static void main(String[] args){ int arr[] = { 1, 2, 3 }; int N = arr.length; int brr[] = { 1, 2 }; int M = brr.length; System.out.print(cntPairsInTwoArray(arr, brr, N, M));}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program to implement# the above approach# Function to count pairs (arr[i], brr[j])# whose product is an even numberdef cntPairsInTwoArray(arr, brr, N, M): # Stores count of odd # numbers in arr[] cntOddArr = 0 # Stores count of odd # numbers in brr[] cntOddBrr = 0 # Traverse the array, arr[] for i in range(N): # If arr[i] is # an odd number if (arr[i] & 1): # Update cntOddArr cntOddArr += 1 # Traverse the array, brr[] for i in range(M): # If brr[i] is # an odd number if (brr[i] & 1): # Update cntOddArr cntOddBrr += 1 # Return pairs whose product # is an even number return (N * M) - (cntOddArr * cntOddBrr)# Driver Codeif __name__ == '__main__': arr = [ 1, 2, 3 ] N = len(arr) brr = [ 1, 2 ] M = len(brr) print(cntPairsInTwoArray(arr, brr, N, M))# This code is contributed by mohit kumar 29 |
C#
// C# program to implement// the above approach using System; class GFG{ // Function to count pairs (arr[i], brr[j])// whose product is an even numberstatic int cntPairsInTwoArray(int[] arr, int[] brr, int N, int M){ // Stores count of odd // numbers in arr[] int cntOddArr = 0; // Stores count of odd // numbers in brr[] int cntOddBrr = 0; // Traverse the array, arr[] for(int i = 0; i < N; i++) { // If arr[i] is // an odd number if (arr[i] % 2 == 1) { // Update cntOddArr cntOddArr += 1; } } // Traverse the array, brr[] for(int i = 0; i < M; i++) { // If brr[i] is // an odd number if (brr[i] % 2 == 1) { // Update cntOddArr cntOddBrr += 1; } } // Return pairs whose product // is an even number return (N * M) - (cntOddArr * cntOddBrr);} // Driver Codepublic static void Main(){ int[] arr = { 1, 2, 3 }; int N = arr.Length; int[] brr = { 1, 2 }; int M = brr.Length; Console.Write(cntPairsInTwoArray( arr, brr, N, M));}}// This code is contributed by code_hunt |
Javascript
<script>// JavaScript program for above approach// Function to count pairs (arr[i], brr[j])// whose product is an even numberfunction cntPairsletwoArray(arr, brr, N, M){ // Stores count of odd // numbers in arr[] let cntOddArr = 0; // Stores count of odd // numbers in brr[] let cntOddBrr = 0; // Traverse the array, arr[] for (let i = 0; i < N; i++) { // If arr[i] is // an odd number if (arr[i] % 2 == 1) { // Update cntOddArr cntOddArr += 1; } } // Traverse the array, brr[] for (let i = 0; i < M; i++) { // If brr[i] is // an odd number if (brr[i] % 2 == 1) { // Update cntOddArr cntOddBrr += 1; } } // Return pairs whose product // is an even number return (N * M) - (cntOddArr * cntOddBrr);}// Driver Code let arr = [ 1, 2, 3 ]; let N = arr.length; let brr = [ 1, 2 ]; let M = brr.length; document.write(cntPairsletwoArray(arr, brr, N, M)); </script> |
Output
4
Time Complexity: O(N)
Space Complexity: O(1)
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!
