Given two integer arrays P[] and Q[], where pi and qj for each 0 <= i < size(P) and 0 <= j < size(Q) represents the line equations x – y = -pi and x + y = qj respectively. The task is to find the number of pairs from P[] and Q[] having integer intersection points.
Examples:
Input: P[] = {1, 3, 2}, Q[] = {3, 0}
Output: 3
The pairs of lines (p, q) having integer intersection points are (1, 3), (2, 0) and (3, 3). Here p is the line parameter of P[] and q is the that of Q[].Input: P[] = {1, 4, 3, 2}, Q[] = {3, 6, 10, 11}
Output: 8
Approach:
- The problem can be solved easily by solving the two equations and analyzing the condition for integer intersection points.
- The two equations are x – y = -p and x + y = q.
- Solving for x and y we get, x = (q-p)/2 and y = (p+q)/2.
- It is clear that integer intersection point is possible if and only if p and q have same parity.
- Let p0 and p1 be the number of even and odd pi respectively.
- Similarly, q0 and q1 for the number of even and odd qi respectively.
- Therefore the required answers is p0 * q0 + p1 * q1.
Below is the implementation of the above approach:
C++
// C++ program to Number of pairs of lines// having integer intersection points#include <bits/stdc++.h>using namespace std;// Count number of pairs of lines// having integer intersection pointint countPairs(int* P, int* Q, int N, int M){ // Initialize arrays to store counts int A[2] = { 0 }, B[2] = { 0 }; // Count number of odd and even Pi for (int i = 0; i < N; i++) A[P[i] % 2]++; // Count number of odd and even Qi for (int i = 0; i < M; i++) B[Q[i] % 2]++; // Return the count of pairs return (A[0] * B[0] + A[1] * B[1]);}// Driver codeint main(){ int P[] = { 1, 3, 2 }, Q[] = { 3, 0 }; int N = sizeof(P) / sizeof(P[0]); int M = sizeof(Q) / sizeof(Q[0]); cout << countPairs(P, Q, N, M); return 0;} |
Java
// Java program to Number of pairs of lines// having integer intersection pointsclass GFG{// Count number of pairs of lines// having integer intersection pointstatic int countPairs(int []P, int []Q, int N, int M){ // Initialize arrays to store counts int []A = new int[2], B = new int[2]; // Count number of odd and even Pi for (int i = 0; i < N; i++) A[P[i] % 2]++; // Count number of odd and even Qi for (int i = 0; i < M; i++) B[Q[i] % 2]++; // Return the count of pairs return (A[0] * B[0] + A[1] * B[1]);}// Driver codepublic static void main(String[] args){ int []P = { 1, 3, 2 }; int []Q = { 3, 0 }; int N = P.length; int M = Q.length; System.out.print(countPairs(P, Q, N, M));}}// This code is contributed by Rajput-Ji |
Python3
# Python3 program to Number of pairs of lines# having eger ersection pos# Count number of pairs of lines# having eger ersection podef countPairs(P, Q, N, M): # Initialize arrays to store counts A = [0] * 2 B = [0] * 2 # Count number of odd and even Pi for i in range(N): A[P[i] % 2] += 1 # Count number of odd and even Qi for i in range(M): B[Q[i] % 2] += 1 # Return the count of pairs return (A[0] * B[0] + A[1] * B[1])# Driver codeP = [1, 3, 2]Q = [3, 0]N = len(P)M = len(Q)print(countPairs(P, Q, N, M))# This code is contributed by mohit kumar 29 |
C#
// C# program to Number of pairs of lines// having integer intersection pointsusing System;class GFG{ // Count number of pairs of lines // having integer intersection point static int countPairs(int []P, int []Q, int N, int M) { // Initialize arrays to store counts int []A = new int[2]; int []B = new int[2]; // Count number of odd and even Pi for (int i = 0; i < N; i++) A[P[i] % 2]++; // Count number of odd and even Qi for (int i = 0; i < M; i++) B[Q[i] % 2]++; // Return the count of pairs return (A[0] * B[0] + A[1] * B[1]); } // Driver code public static void Main() { int []P = { 1, 3, 2 }; int []Q = { 3, 0 }; int N = P.Length; int M = Q.Length; Console.Write(countPairs(P, Q, N, M)); }}// This code is contributed by AnkitRai01 |
Javascript
<script>// Javascript program to Number of // pairs of lines having integer // intersection points// Count number of pairs of lines// having integer intersection pointfunction countPairs(P, Q, N, M){ // Initialize arrays to store counts var A = [0, 0], B = [0, 0]; // Count number of odd and even Pi for(var i = 0; i < N; i++) A[P[i] % 2]++; // Count number of odd and even Qi for(var i = 0; i < M; i++) B[Q[i] % 2]++; // Return the count of pairs return(A[0] * B[0] + A[1] * B[1]);}// Driver codevar P = [ 1, 3, 2 ], Q = [ 3, 0 ];var N = P.length;var M = Q.length;document.write(countPairs(P, Q, N, M));// This code is contributed by rrrtnx</script> |
Output:
3
Time Complexity: O(P + Q)
Auxiliary Space: 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!
