Given two arrays A[] and B[] consisting of N and M integers respectively, the task is to count pairs (A[i], B[j]) such that the product of their count of distinct prime factors is even.
Examples:
Input: A[] = {1, 2, 3}, B[] = {4, 5, 6}, N = 3, M = 3
Output: 2
Explanation:
- Replacing all array elements with the count of their distinct prime factors modifies the arrays to A[] = {0, 1, 1} and B[] = {1, 1, 2}.
- Therefore, total pairs with even product are {{2, 6}, {3, 6}}.
Input: A[] = {1, 7}, B[] = {5, 6}, N = 2, M = 2
Output: 1
Explanation:
- Replacing all array elements with the count of their distinct prime factors modifies the arrays to A[] = {0, 1} and B[] = {1, 2}.
- Therefore, total pairs with even product is {7, 6}.
Naive Approach: The simplest approach is to generate all possible pairs (A[i], B[j]) from both arrays and for each pair, calculate the count of distinct prime factors of the array elements and check if their product is even or not. If found to be true, then increment the count of such pairs.
Time Complexity: O(N5/2)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized by precalculating the count of distinct prime factors of all the numbers up to the largest element from both the arrays and use the following property of product of two numbers:
- Odd * Odd = Odd
- Even * Odd = Even
- Odd * Even = Even
- Even * Even = Even
Follow the steps below to solve the problem:
- First, calculate distinct prime factors of all numbers up to MAX and store it in vector<int> say countDistinct.
- Initialize two variables, say evenCount and oddCount, to store the count of elements with even and odd count of distinct prime factors of the array elements in B[].
- Traverse the array B[]. If, countDistinct[B[i]] = 0, skip this step. If it is odd, increment oddCount by 1. Otherwise, increment evenCount by one.
- Initialize a variable evenPairs to 0.
- Traverse the array A[] and increment evenPairs by evenCount if countDistinct[A[i]] is odd.
- Otherwise, increment evenPairs by evenCount + oddCount.
- Print the value of evenPairs.
Below is the implementation of the above approach:
C++
// C++ implementation of// the above approach#include <bits/stdc++.h>using namespace std;#define MAX 1000000// Function to calculate count of// distinct prime factors of a numbervoid countOfPrimefactors(vector<int>& CountDistinct){ bool prime[MAX + 1]; for (int i = 0; i <= MAX; i++) { CountDistinct[i] = 0; prime[i] = true; } // Sieve of Eratosthenes for (long long int i = 2; i <= MAX; i++) { if (prime[i] == true) { CountDistinct[i] = 1; for (long long int j = i * 2; j <= MAX; j += i) { CountDistinct[j]++; prime[j] = false; } } }}// Function to count pairs with even// product of distinct prime factorsint CountEvenPair(int A[], int B[], int N, int M){ // Stores count of // distinct prime factors vector<int> countDistinct(MAX + 1); countOfPrimefactors(countDistinct); // Stores the count of numbers // with even prime factors in B[] int evenCount = 0; // Stores the count of numbers // with odd prime factors in B[] int oddCount = 0; // Even Product Pairs int evenPairs = 0; // Traverse the array B[] for (int i = 0; i < M; i++) { // Since, product has to be // positive i.e > 0 if (countDistinct[B[i]] == 0) continue; // If count of prime factors is odd if (countDistinct[B[i]] & 1) { // Increment oddCount by 1 oddCount++; } else { // Increment evenCount by 1 evenCount++; } } for (int i = 0; i < N; i++) { // Since, product has to be // positive i.e > 0 if (countDistinct[A[i]] == 0) continue; // If count of prime factors is odd if (countDistinct[A[i]] & 1) { // odd * even = even evenPairs += (evenCount); } // If count of prime factors is even else { // even * odd = even // even * even = even evenPairs += evenCount + oddCount; } } return evenPairs;}// Driver Codeint main(){ int A[] = { 1, 2, 3 }; int B[] = { 4, 5, 6 }; int N = sizeof(A) / sizeof(A[0]); int M = sizeof(B) / sizeof(B[0]); cout << CountEvenPair(A, B, N, M); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{ static int MAX = 1000000; // Function to calculate count of // distinct prime factors of a number static void countOfPrimefactors(int[] CountDistinct) { boolean[] prime = new boolean[MAX + 1]; for (int i = 0; i <= MAX; i++) { CountDistinct[i] = 0; prime[i] = true; } // Sieve of Eratosthenes for (int i = 2; i <= MAX; i++) { if (prime[i] == true) { CountDistinct[i] = 1; for (int j = i * 2; j <= MAX; j += i) { CountDistinct[j]++; prime[j] = false; } } } } // Function to count pairs with even // product of distinct prime factors static int CountEvenPair(int A[], int B[], int N, int M) { // Stores count of // distinct prime factors int[] countDistinct = new int[(MAX + 1)]; countOfPrimefactors(countDistinct); // Stores the count of numbers // with even prime factors in B[] int evenCount = 0; // Stores the count of numbers // with odd prime factors in B[] int oddCount = 0; // Even Product Pairs int evenPairs = 0; // Traverse the array B[] for (int i = 0; i < M; i++) { // Since, product has to be // positive i.e > 0 if (countDistinct[B[i]] == 0) continue; // If count of prime factors is odd if ((countDistinct[B[i]] & 1) != 0) { // Increment oddCount by 1 oddCount++; } else { // Increment evenCount by 1 evenCount++; } } for (int i = 0; i < N; i++) { // Since, product has to be // positive i.e > 0 if (countDistinct[A[i]] == 0) continue; // If count of prime factors is odd if ((countDistinct[A[i]] & 1) != 0) { // odd * even = even evenPairs += (evenCount); } // If count of prime factors is even else { // even * odd = even // even * even = even evenPairs += evenCount + oddCount; } } return evenPairs; } // Driver Code public static void main(String[] args) { int A[] = { 1, 2, 3 }; int B[] = { 4, 5, 6 }; int N = A.length; int M = B.length; System.out.println(CountEvenPair(A, B, N, M)); }}// This code is contributed by sanjoy_62. |
Python3
# Python 3 implementation of# the above approachMAX = 1000000# Function to calculate count of# distinct prime factors of a numberdef countOfPrimefactors(CountDistinct): global MAX prime = [0 for i in range(MAX + 1)] for i in range(MAX+1): CountDistinct[i] = 0 prime[i] = True # Sieve of Eratosthenes for i in range(2,MAX+1,1): if (prime[i] == True): CountDistinct[i] = 1 for j in range(i * 2,MAX+1,i): CountDistinct[j] += 1 prime[j] = False # Function to count pairs with even# product of distinct prime factorsdef CountEvenPair(A, B, N, M): global MAX # Stores count of # distinct prime factors countDistinct = [0 for i in range(MAX + 1)] countOfPrimefactors(countDistinct) # Stores the count of numbers # with even prime factors in B[] evenCount = 0 # Stores the count of numbers # with odd prime factors in B[] oddCount = 0 # Even Product Pairs evenPairs = 0 # Traverse the array B[] for i in range(M): # Since, product has to be # positive i.e > 0 if (countDistinct[B[i]] == 0): continue # If count of prime factors is odd if (countDistinct[B[i]] & 1): # Increment oddCount by 1 oddCount += 1 else: # Increment evenCount by 1 evenCount += 1 for i in range(N): # Since, product has to be # positive i.e > 0 if (countDistinct[A[i]] == 0): continue # If count of prime factors is odd if (countDistinct[A[i]] & 1): # odd * even = even evenPairs += (evenCount) # If count of prime factors is even else: # even * odd = even # even * even = even evenPairs += evenCount + oddCount return evenPairs# Driver Codeif __name__ == '__main__': A = [1, 2, 3] B = [4, 5, 6] N = len(A) M = len(B) print(CountEvenPair(A, B, N, M)) # This code is contributed by SURENDRA_GANGWAR. |
C#
// C# program for the above approachusing System;public class GFG{ static int MAX = 1000000; // Function to calculate count of // distinct prime factors of a number static void countOfPrimefactors(int[] CountDistinct) { bool[] prime = new bool[MAX + 1]; for (int i = 0; i <= MAX; i++) { CountDistinct[i] = 0; prime[i] = true; } // Sieve of Eratosthenes for (int i = 2; i <= MAX; i++) { if (prime[i] == true) { CountDistinct[i] = 1; for (int j = i * 2; j <= MAX; j += i) { CountDistinct[j]++; prime[j] = false; } } } } // Function to count pairs with even // product of distinct prime factors static int CountEvenPair(int []A, int []B, int N, int M) { // Stores count of // distinct prime factors int[] countDistinct = new int[(MAX + 1)]; countOfPrimefactors(countDistinct); // Stores the count of numbers // with even prime factors in B[] int evenCount = 0; // Stores the count of numbers // with odd prime factors in B[] int oddCount = 0; // Even Product Pairs int evenPairs = 0; // Traverse the array B[] for (int i = 0; i < M; i++) { // Since, product has to be // positive i.e > 0 if (countDistinct[B[i]] == 0) continue; // If count of prime factors is odd if ((countDistinct[B[i]] & 1) != 0) { // Increment oddCount by 1 oddCount++; } else { // Increment evenCount by 1 evenCount++; } } for (int i = 0; i < N; i++) { // Since, product has to be // positive i.e > 0 if (countDistinct[A[i]] == 0) continue; // If count of prime factors is odd if ((countDistinct[A[i]] & 1) != 0) { // odd * even = even evenPairs += (evenCount); } // If count of prime factors is even else { // even * odd = even // even * even = even evenPairs += evenCount + oddCount; } } return evenPairs; } // Driver Code public static void Main(string[] args) { int []A = { 1, 2, 3 }; int []B = { 4, 5, 6 }; int N = A.Length; int M = B.Length; Console.WriteLine(CountEvenPair(A, B, N, M)); }}// This code is contributed by AnkThon |
Javascript
<script>// js program for the above approach let countDistinct = Array(1000000 + 1);// Function to calculate count of// distinct prime factors of a numberfunction countOfPrimefactors(CountDistinct){ let MAX = 1000000; let prime = Array(MAX + 1); for (let i = 0; i <= MAX; i++) { CountDistinct[i] = 0; prime[i] = true; } // Sieve of Eratosthenes for (let i = 2; i <= MAX; i++) { if (prime[i] == true) { CountDistinct[i] = 1; for (let j = i * 2; j <= MAX; j += i) { CountDistinct[j]++; prime[j] = false; } } }}// Function to count pairs with even// product of distinct prime factorsfunction CountEvenPair(A,B,N,M){ let MAX = 1000000; // Stores count of // distinct prime factors countOfPrimefactors(countDistinct); // Stores the count of numbers // with even prime factors in B[] let evenCount = 0; // Stores the count of numbers // with odd prime factors in B[] let oddCount = 0; // Even Product Pairs let evenPairs = 0; // Traverse the array B[] for (let i = 0; i < M; i++) { // Since, product has to be // positive i.e > 0 if (countDistinct[B[i]] == 0) continue; // If count of prime factors is odd if ((countDistinct[B[i]] & 1) != 0) { // Increment oddCount by 1 oddCount++; } else { // Increment evenCount by 1 evenCount++; } } for (let i = 0; i < N; i++) { // Since, product has to be // positive i.e > 0 if (countDistinct[A[i]] == 0) continue; // If count of prime factors is odd if ((countDistinct[A[i]] & 1) != 0) { // odd * even = even evenPairs += (evenCount); } // If count of prime factors is even else { // even * odd = even // even * even = even evenPairs += evenCount + oddCount; } } return evenPairs;}// Driver Codelet A = [1, 2, 3];let B = [4, 5, 6];let N = A.length;let M = B.length;document.write(CountEvenPair(A, B, N, M));</script> |
Output:
2
Time Complexity: O(N * log(N))
Auxiliary Space: O(N)
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!
