Skip to content
Related Articles

Related Articles

Number of ordered points pair satisfying line equation

View Discussion
Improve Article
Save Article
  • Difficulty Level : Expert
  • Last Updated : 12 Aug, 2022
View Discussion
Improve Article
Save Article

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

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. 

Implementation:

C++




// CPP code to count the number of ordered
// pairs satisfying Line Equation
#include <bits/stdc++.h>
 
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[0]);
 
    // equation of line is y = mx + c
    int m = 1, c = 1;
    cout << findOrderedPoints(arr, n, m, c);
    return 0;
}

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




<?php
// PHP 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*/
function 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 */
function 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 = 0; $i < $n; $i++)
    {
        for ($j = 0; $j < $n; $j++)
        {
            // (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++;
        }
    }
    return $counter;
}
 
// Driver Code
$arr = array( 1, 2, 3, 4, 2 );
$n = count($arr);
 
// equation of line
// is y = mx + c
$m = 1; $c = 1;
echo (findOrderedPoints($arr, $n, $m, $c));
 
// This code is contributed by
// Manish Shaw (manishshaw1)
?>

Javascript




<script>
      // JavaScript code to find number of ordered
      // points 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
      function isValid(arr, i, j, m, c)
      {
       
        // check if i equals to j
        if (i == j) return false;
 
        // Equation LHS = y,
        // and RHS = mx + c
        var lhs = arr[j];
        var 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 */
      function findOrderedPoints(arr, n, m, c) {
        var counter = 0;
 
        // for every possible (i, j) check
        // if (a[i], a[j]) satisfies the
        // equation y = mx + c
        for (var i = 0; i < n; i++)
        {
          for (var j = 0; j < n; j++)
          {
           
            // (firstIndex, secondIndex)
            // is same as (i, j)
            var firstIndex = i,
              secondIndex = j;
 
            // check if (firstIndex,
            // secondIndex) is a valid point
            if (isValid(arr, firstIndex, secondIndex, m, c)) counter++;
          }
        }
        return counter;
      }
 
      // Driver Code
      var arr = [1, 2, 3, 4, 2];
      var n = arr.length;
 
      // equation of line is y = mx + c
      var m = 1,
        c = 1;
      document.write(findOrderedPoints(arr, n, m, c));
       
      // This code is contributed by rdtank.
    </script>

Output

5

Complexity Analysis: 

  • Time Complexity : O(n2)
  • Auxiliary Space: O(1)

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.
Implementation:

C++




// CPP code to find number of ordered
// points satisfying line equation
#include <bits/stdc++.h>
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<int, int> 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[0]);
    int m = 1, c = 1;
    cout << findOrderedPoints(arr, n, m, c);
    return 0;
}

Java




// Java program to find number of ordered
// points satisfying line equation
 
import java.io.*;
import java.util.*;
 
class GFG {
     
    /* 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;
  
        // map stores the frequency
        // of arr[i] for all i
        HashMap<Integer,Integer> frequency = new HashMap<>();
         
        for(int i=0;i<n;i++){
            if(frequency.get(arr[i])==null){
                frequency.put(arr[i],1);
            }else{
                frequency.put(arr[i],frequency.get(arr[i])+1);
            }
        }
         
        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.get(yCoordinate) !=null)
                counter += frequency.get(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
    public static void main (String[] args) {
        int arr[] = { 1, 2, 3, 4, 2 };
        int n=5,m=1,c=1;
        System.out.println(findOrderedPoints(arr,n,m,c));       
    }
}
 
//This code is contributed by shruti456rawal

Python3




# Python code to find number of ordered
# points satisfying line equation
 
""" 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
 
    # map stores the frequency
    # of arr[i] for all i
    frequency = dict()
    for i in range(n):
        if(arr[i] in frequency):
            frequency[arr[i]] += 1
        else:
            frequency[arr[i]] = 1
 
    for i in range(n):
        xCoordinate = arr[i]
        yCoordinate = (m * arr[i] + c)
 
        # if for a[i](xCoordinate),
        # a yCoordinate exists in the map
        # add the frequency of yCoordinate
        # to the counter
        # console.log(counter);
        if (yCoordinate in frequency):
            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])
        # console.log(counter);
        if (xCoordinate == yCoordinate):
            counter -= 1
    return counter
 
 
# Driver Code
arr = [1, 2, 3, 4, 2]
n = len(arr)
m = 1
c = 1
print(findOrderedPoints(arr, n, m, c))
 
# The code is contributed by Saurabh Jaiswal

Javascript




// JavaScript code to find number of ordered
// points satisfying line equation
 
/* Returns the number of ordered pairs
   (i, j) for which point (arr[i], arr[j])
   satisfies the equation of the line
   y = mx + c */
function findOrderedPoints(arr, n, m, c)
{
    let counter = 0;
 
    // map stores the frequency
    // of arr[i] for all i
    let frequency = new Map();   
    for (let i = 0; i < n; i++){
        if(frequency.has(arr[i])){
            frequency.set(arr[i], frequency.get(arr[i]) + 1);
        }
        else{
            frequency.set(arr[i], 1);
        }
    }
 
    for (let i = 0; i < n; i++)
    {
        let xCoordinate = arr[i];
        let yCoordinate = (m * arr[i] + c);
 
        // if for a[i](xCoordinate),
        // a yCoordinate exists in the map
        // add the frequency of yCoordinate
        // to the counter
        // console.log(counter);
        if (frequency.has(yCoordinate))
            counter += frequency.get(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])
        // console.log(counter);
        if (xCoordinate == yCoordinate)
            counter--;
    }
    return counter;
}
 
// Driver Code
let arr = [1, 2, 3, 4, 2];
let n = arr.length;
let m = 1, c = 1;
console.log(findOrderedPoints(arr, n, m, c));
 
// The code is contributed by Nidhi goel

C#




using System;
using System.Collections.Generic;
 
public static class GFG {
    // C# code to find number of ordered
    // points satisfying line equation
 
    /* Returns the number of ordered pairs
       (i, j) for which point (arr[i], arr[j])
       satisfies the equation of the line
       y = mx + c */
    public static int findOrderedPoints(int[] arr, int n,
                                        int m, int c)
    {
        int counter = 0;
 
        // map stores the frequency
        // of arr[i] for all i
        Dictionary<int, int> frequency
            = new Dictionary<int, int>();
 
        for (int i = 0; i < n; i++) {
            if (frequency.ContainsKey(arr[i])) {
                var val = frequency[arr[i]];
                frequency.Remove(arr[i]);
                frequency.Add(arr[i], val + 1);
            }
            else {
                frequency.Add(arr[i], 1);
            }
        }
 
        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.ContainsKey(yCoordinate)) {
                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
    public static void Main()
    {
        int[] arr = { 1, 2, 3, 4, 2 };
        int n = arr.Length;
        int m = 1;
        int c = 1;
        Console.Write(findOrderedPoints(arr, n, m, c));
    }
}
 
// The code is contributed by Aarti_Rathi

Output

5

Time Complexity : O(n) 


My Personal Notes arrow_drop_up
Recommended Articles
Page :

Start Your Coding Journey Now!