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 pointsExplanation : 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 Codeint 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 equationimport 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 jdef 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 Codearr = [ 1, 2, 3, 4, 2 ]n = len(arr)# equation of line is y = mx + cm = 1c = 1print (findOrderedPoints(arr, n, m, c))# This code is contributed by Manish Shaw# (manishshaw1) |
C#
// C# code to find number of ordered// points satisfying line equationusing 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 Codeint 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 equationimport 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 Codearr = [1, 2, 3, 4, 2]n = len(arr)m = 1c = 1print(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 Codelet 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), where n is the size of the given array.
Auxiliary Space: O(n) because it is using extra space for unoredered_map frequency.
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!
