Number of ordered points pair satisfying line equation

Given an array of n integers, slope of a line i. e., m and the intercept of the line i.e c, Count the number of ordered pairs(i, j) of points where i ≠ j, such that point (Ai, Aj) satisfies the line formed with given slope and intercept.
Note : The equation of the line is y = mx + c, where m is the slope of the line and c is the intercept.

Examples :

Input : m = 1, c = 1, arr[] = [ 1, 2, 3, 4, 2 ]
Output : 5 ordered points
Explanation : The equation of the line with given slope and intercept is : y = x + 1. The Number of pairs (i, j), for which (arri, arrj) satisfies the above equation of the line are : (1, 2), (1, 5), (2, 3), (3, 4), (5, 3).

Input : m = 2, c = 1, arr[] = [ 1, 2, 3, 4, 2, 5 ]
Output : 3 ordered points

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Method 1 (Brute Force):
Generate all possible pairs (i, j) and check if a particular ordered pair (i, j) is such that, (arri, arrj) satisfies the given equation of the line y = mx + c, and i ≠ j. If the point is valid(a point is valid if the above condition is satisfied), increment the counter which stores the total number of valid points.

C++

 // CPP code to count the number of ordered // pairs satisfying Line Equation #include    using namespace std;    /* Checks if (i, j) is valid, a point (i, j)    is valid if point (arr[i], arr[j])    satisfies the equation y = mx + c And     i is not equal to j*/ bool isValid(int arr[], int i, int j,               int m, int c) {        // check if i equals to j     if (i == j)          return false;                   // Equation LHS = y, and RHS = mx + c     int lhs = arr[j];         int rhs = m * arr[i] + c;        return (lhs == rhs); }    /* Returns the number of ordered pairs    (i, j) for which point (arr[i], arr[j])    satisfies the equation of the line     y = mx + c */ int findOrderedPoints(int arr[], int n,                        int m, int c) {        int counter = 0;        // for every possible (i, j) check     // if (a[i], a[j]) satisfies the      // equation y = mx + c     for (int i = 0; i < n; i++)      {         for (int j = 0; j < n; j++)          {             // (firstIndex, secondIndex)              // is same as (i, j)             int firstIndex = i, secondIndex = j;                // check if (firstIndex,              // secondIndex) is a valid point             if (isValid(arr, firstIndex, secondIndex, m, c))                  counter++;         }     }     return counter; }    // Driver Code int main() {     int arr[] = { 1, 2, 3, 4, 2 };     int n = sizeof(arr) / sizeof(arr);        // equation of line is y = mx + c     int m = 1, c = 1;     cout << findOrderedPoints(arr, n, m, c);     return 0; }

/div>

Java

 // Java code to find number of ordered // points satisfying line equation import java.io.*;    public class GFG {            // Checks if (i, j) is valid,     // a point (i, j) is valid if      // point (arr[i], arr[j])      // satisfies the equation      // y = mx + c And      // i is not equal to j     static boolean isValid(int []arr, int i,                          int j, int m, int c)     {                // check if i equals to j         if (i == j)              return false;                               // Equation LHS = y,         // and RHS = mx + c         int lhs = arr[j];          int rhs = m * arr[i] + c;                return (lhs == rhs);     }            /* Returns the number of ordered pairs     (i, j) for which point (arr[i], arr[j])     satisfies the equation of the line      y = mx + c */     static int findOrderedPoints(int []arr,                         int n, int m, int c)     {                int counter = 0;                // for every possible (i, j) check         // if (a[i], a[j]) satisfies the          // equation y = mx + c         for (int i = 0; i < n; i++)          {             for (int j = 0; j < n; j++)              {                                    // (firstIndex, secondIndex)                  // is same as (i, j)                 int firstIndex = i,                    secondIndex = j;                        // check if (firstIndex,                  // secondIndex) is a                  // valid point                 if (isValid(arr, firstIndex,                           secondIndex, m, c))                      counter++;             }         }         return counter;     }            // Driver Code     public static void main(String args[])     {         int []arr = { 1, 2, 3, 4, 2 };         int n = arr.length;                // equation of line is y = mx + c         int m = 1, c = 1;         System.out.print(            findOrderedPoints(arr, n, m, c));     } }    // This code is contributed by // Manish Shaw (manishshaw1)

Python3

 # Python code to count the number of ordered # pairs satisfying Line Equation    # Checks if (i, j) is valid, a point (i, j) # is valid if point (arr[i], arr[j]) # satisfies the equation y = mx + c And  # i is not equal to j def isValid(arr, i, j, m, c) :        # check if i equals to j     if (i == j) :         return False                   # Equation LHS = y, and RHS = mx + c     lhs = arr[j];     rhs = m * arr[i] + c        return (lhs == rhs)    # Returns the number of ordered pairs # (i, j) for which point (arr[i], arr[j]) # satisfies the equation of the line  # y = mx + c */ def findOrderedPoints(arr, n, m, c) :        counter = 0        # for every possible (i, j) check     # if (a[i], a[j]) satisfies the      # equation y = mx + c     for i in range(0, n) :         for j in range(0, n) :             # (firstIndex, secondIndex)              # is same as (i, j)             firstIndex = i             secondIndex = j                # check if (firstIndex,              # secondIndex) is a valid point             if (isValid(arr, firstIndex,                       secondIndex, m, c)) :                  counter = counter + 1        return counter    # Driver Code arr = [ 1, 2, 3, 4, 2 ] n = len(arr)    # equation of line is y = mx + c m = 1 c = 1 print (findOrderedPoints(arr, n, m, c))    # This code is contributed by Manish Shaw # (manishshaw1)

C#

 // C# code to find number of ordered // points satisfying line equation using System; class GFG {            // Checks if (i, j) is valid,     // a point (i, j) is valid if      // point (arr[i], arr[j])      // satisfies the equation      // y = mx + c And      // i is not equal to j     static bool isValid(int []arr, int i,                       int j, int m, int c)     {                // check if i equals to j         if (i == j)              return false;                               // Equation LHS = y,         // and RHS = mx + c         int lhs = arr[j];          int rhs = m * arr[i] + c;                return (lhs == rhs);     }            /* Returns the number of ordered pairs       (i, j) for which point (arr[i], arr[j])       satisfies the equation of the line         y = mx + c */     static int findOrderedPoints(int []arr, int n,                                       int m, int c)     {                int counter = 0;                // for every possible (i, j) check         // if (a[i], a[j]) satisfies the          // equation y = mx + c         for (int i = 0; i < n; i++)          {             for (int j = 0; j < n; j++)              {                                    // (firstIndex, secondIndex)                  // is same as (i, j)                 int firstIndex = i, secondIndex = j;                        // check if (firstIndex,                  // secondIndex) is a valid point                 if (isValid(arr, firstIndex, secondIndex, m, c))                      counter++;             }         }         return counter;     }            // Driver Code     public static void Main()     {         int []arr = { 1, 2, 3, 4, 2 };         int n = arr.Length;                // equation of line is y = mx + c         int m = 1, c = 1;         Console.Write(findOrderedPoints(arr, n, m, c));     } }    // This code is contributed by // Manish Shaw (manishshaw1)

PHP



Output :

5

Time Complexity : O(n2)

Method 2 (Efficient) :
Given a x coordinate of a point, for each x there is a unique value of y and the value of y is nothing but m * x + c. So, for each possible x coordinate of the array arr, calculate how many times the unique value of y which satisfies the equation of the line occurs in that array. Store count of all the integers of array, arr in a map. Now, for each value, arri, add to the answer, the number of occurrences of m * arri + c. For a given i, m * a[i] + c occurs x times in the array, then, add x to our counter for total valid points, but need to check that if a[i] = m * a[i] + c then, it is obvious that since this occurs x times in the array then one occurrence is at the ith index and rest (x – 1) occurrences are the valid y coordinates so add (x – 1) to our points counter.

 // CPP code to find number of ordered // points satisfying line equation #include using namespace std;    /* Returns the number of ordered pairs    (i, j) for which point (arr[i], arr[j])    satisfies the equation of the line     y = mx + c */ int findOrderedPoints(int arr[], int n,                        int m, int c) {     int counter = 0;        // map stores the frequency      // of arr[i] for all i     unordered_map frequency;        for (int i = 0; i < n; i++)          frequency[arr[i]]++;        for (int i = 0; i < n; i++)      {         int xCoordinate = arr[i];         int yCoordinate = (m * arr[i] + c);            // if for a[i](xCoordinate),          // a yCoordinate exists in the map         // add the frequency of yCoordinate         // to the counter            if (frequency.find(yCoordinate) !=              frequency.end())              counter += frequency[yCoordinate];            // check if xCoordinate = yCoordinate,         // if this is true then since we only         // want (i, j) such that i != j, decrement         // the counter by one to avoid points          // of type (arr[i], arr[i])         if (xCoordinate == yCoordinate)              counter--;     }     return counter; }    // Driver Code int main() {     int arr[] = { 1, 2, 3, 4, 2 };     int n = sizeof(arr) / sizeof(arr);     int m = 1, c = 1;     cout << findOrderedPoints(arr, n, m, c);     return 0; }

Output:

5

Time Complexity : O(n)