Given two arrays A[] and B[] consisting of N integers, the task is to count pairs (A[i], B[j]) with even and odd product and print the maximum of the two counts.
Examples:
Input: A[] = {1, 2, 3}, B[] = {4, 5, 6}
Output: 7
Explanation:
Pairs with odd product count are: (1, 5) (3, 5). Therefore, number of pairs with odd product = 2.
Pairs with even product count are: (1, 4) (1, 6) (2, 4) (2, 5) (2, 6) (3, 4) (3, 6). Therefore, number of pairs with even product = 7
Therefore, the maximum of the two counts is 7. Hence, the output 7.Input: A[] = {1, 5, 9}, B[] = {1, 7, 3}
Output: 9
Explanation:
Pairs with odd product count are: (1, 1) (1, 7) (1, 3) (5, 1) (5, 7) (5, 3) (9, 1) (9, 7) (9, 3). Therefore, number of pairs with odd product = 9
No pair with even product count exists.
Therefore, the output 9.
Brute Force Approach:
Brute force approach to solve this problem is to iterate over all possible pairs (A[i], B[j]) and count the number of pairs with odd and even products. We can use two variables, one to store the count of pairs with odd product and the other to store the count of pairs with even product. We can then return the maximum of the two counts.
Below is the implementation of the above approach:
C++
// C++ program for above approach #include <bits/stdc++.h> using namespace std; // Function to return the maximum // count of odd count pair or // even count pair int maxcountpair( int A[], int B[], int N) { int odd_pairs = 0, even_pairs = 0; for ( int i=0; i<N; i++) { for ( int j=0; j<N; j++) { int product = A[i] * B[j]; if (product % 2 == 0) even_pairs++; else odd_pairs++; } } return max(odd_pairs, even_pairs); } // Driver Code int main() { int A[] = { 1, 2, 3 }; int B[] = { 4, 5, 6 }; int N = sizeof (A) / sizeof (A[0]); // Function Call cout << maxcountpair(A, B, N); return 0; } |
Java
import java.util.*; class Main { // Function to return the maximum // count of odd count pair or // even count pair static int maxcountpair( int A[], int B[], int N) { int odd_pairs = 0 , even_pairs = 0 ; for ( int i= 0 ; i<N; i++) { for ( int j= 0 ; j<N; j++) { int product = A[i] * B[j]; if (product % 2 == 0 ) even_pairs++; else odd_pairs++; } } return Math.max(odd_pairs, even_pairs); } // Driver Code public static void main(String[] args) { int A[] = { 1 , 2 , 3 }; int B[] = { 4 , 5 , 6 }; int N = A.length; // Function Call System.out.println(maxcountpair(A, B, N)); } } |
Python3
# Function to return the maximum # count of odd count pair or # even count pair def maxcountpair(A, B, N): odd_pairs = 0 even_pairs = 0 for i in range (N): for j in range (N): product = A[i] * B[j] if product % 2 = = 0 : even_pairs + = 1 else : odd_pairs + = 1 return max (odd_pairs, even_pairs) # Driver Code if __name__ = = "__main__" : A = [ 1 , 2 , 3 ] B = [ 4 , 5 , 6 ] N = len (A) # Function Call print (maxcountpair(A, B, N)) |
C#
using System; public class Program { // Function to return the maximum // count of odd count pair or // even count pair public static int MaxCountPair( int [] A, int [] B, int N) { int odd_pairs = 0; int even_pairs = 0; for ( int i = 0; i < N; i++) { for ( int j = 0; j < N; j++) { int product = A[i] * B[j]; if (product % 2 == 0) { even_pairs += 1; } else { odd_pairs += 1; } } } return Math.Max(odd_pairs, even_pairs); } // Driver Code public static void Main() { int [] A = { 1, 2, 3 }; int [] B = { 4, 5, 6 }; int N = A.Length; // Function Call Console.WriteLine(MaxCountPair(A, B, N)); } } |
Javascript
// Function to return the maximum count of odd count pair or even count pair function maxcountpair(A, B, N) { let odd_pairs = 0; let even_pairs = 0; for (let i = 0; i < N; i++) { for (let j = 0; j < N; j++) { const product = A[i] * B[j]; if (product % 2 === 0) { even_pairs++; } else { odd_pairs++; } } } return Math.max(odd_pairs, even_pairs); } // Driver Code const A = [1, 2, 3]; const B = [4, 5, 6]; const N = A.length; // Function Call console.log(maxcountpair(A, B, N)); |
7
Time Complexity: O(N^2)
Auxiliary Space: O(1)
Efficient solution: The above approach can be optimized by observing that only multiplying a pair of odd integers results in an odd number. Otherwise, an even integer will be generated. Follow the steps below to solve the problem:
- Initialize variables oddcount, evencount, and oddCountB to 0 to store the count of odd product pairs, even product pairs, and the count of odd numbers in the array B[] respectively.
- Traverse the array B[] and increment oddCountB if element is odd. Now the value of (N – oddCountB) gives the number of even elements in the array B[].
- Traverse the array A[] and do the following:
- If the current element is even, increment evencount by N since multiplying any number in B[] will result in even product pairs.
- Otherwise, increment evencount by (N – oddCountB) since the even numbers in B[] when multiplied with an odd number in A[], gives (N – oddCountB) pairs and increment oddcount by oddCountB, since odd numbers in B[] multiplying with an odd number in A[] gives the count of odd product pair.
- After completing the above steps, print the maximum of the count of oddcount and evencount as the result.
Below is the implementation of the above approach:
C++
// C++ program for above approach #include <bits/stdc++.h> using namespace std; // Function to return the maximum // count of odd count pair or // even count pair int maxcountpair( int A[], int B[], int N) { // Stores odd count, even count // pairs and odd numbers in B[] int oddcount = 0, evencount = 0; int oddCountB = 0; // Traverse the array B[] for ( int i = 0; i < N; i++) { // If B[i] is an odd number if (B[i] & 1) // Increment oddCountB by 1 oddCountB += 1; } // Traverse the array A[] for ( int i = 0; i < N; i++) { // If A[i] is an odd number if (A[i] & 1) { oddcount += oddCountB; evencount += (N - oddCountB); } // If A[i] is even else evencount += N; } // Return maximum count of odd // and even pairs return max(oddcount, evencount); } // Driver Code int main() { int A[] = { 1, 2, 3 }; int B[] = { 4, 5, 6 }; int N = sizeof (A) / sizeof (A[0]); // Function Call cout << maxcountpair(A, B, N); return 0; } |
C
// C program for above approach #include <stdio.h> // Function to return the // maximum of two numbers int max( int num1, int num2) { return (num1 > num2) ? num1 : num2; } // Function to return the maximum count of // odd count pair or even count pair int maxcountpair( int A[], int B[], int N) { // Stores odd count, even count // pairs and odd numbers in B[] int oddcount = 0, evencount = 0; int oddCountB = 0; // Traverse the array B[] for ( int i = 0; i < N; i++) { // If B[i] is an odd number if (B[i] & 1) // Increment oddCountB by 1 oddCountB += 1; } // Traverse the array A[] for ( int i = 0; i < N; i++) { // If A[i] is an odd number if (A[i] & 1) { oddcount += oddCountB; evencount += (N - oddCountB); } // If A[i] is even else evencount += N; } // Return maximum count of odd // and even pairs return max(oddcount, evencount); } // Driver Code int main() { int A[] = { 1, 2, 3 }; int B[] = { 4, 5, 6 }; int N = sizeof (A) / sizeof (A[0]); printf ( "%d" , maxcountpair(A, B, N)); return 0; } // This code is contributed by sourav singh |
Java
// Java program for above approach import java.io.*; class GFG{ // Function to return the maximum count of // odd count pair or even count pair static int maxcountpair( int A[], int B[], int N) { // Stores odd count, even count // pairs and odd numbers in B[] int oddcount = 0 , evencount = 0 ; int oddCountB = 0 ; // Traverse the array B[] for ( int i = 0 ; i < N; i++) { // If B[i] is an odd number if (B[i] % 2 == 1 ) // Increment oddCountB by 1 oddCountB += 1 ; } // Traverse the array A[] for ( int i = 0 ; i < N; i++) { // If A[i] is an odd number if (A[i] % 2 == 1 ) { oddcount += oddCountB; evencount += (N - oddCountB); } // If A[i] is even else evencount += N; } // Return maximum count of odd // and even pairs return (oddcount > evencount) ? oddcount : evencount; } // Driver Code public static void main(String[] args) { int A[] = { 1 , 2 , 3 }; int B[] = { 4 , 5 , 6 }; int N = A.length; System.out.print(maxcountpair(A, B, N)); } } // This code is contributed by sourav singh |
Python3
# Python3 program for above approach # Function to return the maximum count of # odd count pair or even count pair def maxcountpair(A, B, N): # Function to return the maximum count of # odd count pair or even count pair oddcount = 0 evencount = 0 oddCountB = 0 # Traverse the array, B[] for i in range ( 0 , N): # If B[i] is an odd number if B[i] % 2 = = 1 : oddCountB + = 1 # Traverse the array, A[] for i in range ( 0 , N): # If A[i] is an odd number if A[i] % 2 = = 1 : oddcount + = oddCountB evencount + = (N - oddCountB) else : evencount + = N # Return maximum count of odd # and even pairs return max (oddcount, evencount) # Driver Code A = [ 1 , 2 , 3 ] B = [ 4 , 5 , 6 ] N = len (A) print (maxcountpair(A, B, N)) # This code is contributed by sourav singh |
C#
// C# program for above approach using System; using System.Collections.Generic; class GFG{ // Function to return the maximum count of // odd count pair or even count pair static int maxcountpair( int [] A, int [] B, int N) { // Stores odd count, even count // pairs and odd numbers in B[] int oddcount = 0, evencount = 0; int oddCountB = 0; // Traverse the array B[] for ( int i = 0; i < N; i++) { // If B[i] is an odd number if (B[i] % 2 == 1) // Increment oddCountB by 1 oddCountB += 1; } // Traverse the array A[] for ( int i = 0; i < N; i++) { // If A[i] is an odd number if (A[i] % 2 == 1) { oddcount += oddCountB; evencount += (N - oddCountB); } // If A[i] is even else evencount += N; } // Return maximum count of odd // and even pairs return (oddcount > evencount) ? oddcount : evencount; } // Driver Code public static void Main(String[] args) { int [] A = { 1, 2, 3 }; int [] B = { 4, 5, 6 }; int N = A.Length; // Function call Console.Write(maxcountpair(A, B, N)); } } // This code is contributed by sourav singh |
Javascript
<script> // JavaScript program for above approach // Function to return the maximum // count of odd count pair or // even count pair function maxcountpair(A, B, N) { // Stores odd count, even count // pairs and odd numbers in B[] let oddcount = 0, evencount = 0; let oddCountB = 0; // Traverse the array B[] for (let i = 0; i < N; i++) { // If B[i] is an odd number if (B[i] & 1) // Increment oddCountB by 1 oddCountB += 1; } // Traverse the array A[] for (let i = 0; i < N; i++) { // If A[i] is an odd number if (A[i] & 1) { oddcount += oddCountB; evencount += (N - oddCountB); } // If A[i] is even else evencount += N; } // Return maximum count of odd // and even pairs return Math.max(oddcount, evencount); } // Driver Code let A = [ 1, 2, 3 ]; let B = [ 4, 5, 6 ]; let N = A.length; // Function Call document.write(maxcountpair(A, B, N)); // This code is contributed by Surbhi Tyagi. </script> |
7
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!