Number of pairs of lines having integer intersection points

0 0 4 minutes read

Given two integer arrays P[] and Q[], where p_i and q_j for each 0 <= i < size(P) and 0 <= j < size(Q) represents the line equations x – y = -p_i and x + y = q_j 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 p₀ and p₁ be the number of even and odd p_i respectively.
Similarly, q₀ and q₁ for the number of even and odd q_i respectively.
Therefore the required answers is p₀ * q₀ + p₁ * q₁.

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 point
int 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 code
int 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 points
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], 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(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 po
def 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 code
 
P = [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 points
using 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 point
function 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 code
var 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:

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 zambiatek!