Dada una array de n enteros, la pendiente de una línea, es decir, m y la intersección de la línea, es decir, c, cuente el número de pares ordenados (i, j) de puntos donde i ≠ j, tal que el punto (A i , A j ) satisface la línea formada con la pendiente y el intercepto dados.
Nota : La ecuación de la línea es y = mx + c, donde m es la pendiente de la línea y c es la intersección.
Ejemplos:
Entrada : m = 1, c = 1, arr[] = [ 1, 2, 3, 4, 2 ]
Salida : 5 puntos ordenados
Explicación : La ecuación de la recta con pendiente e intersección dados es : y = x + 1. El Número de pares (i, j), para los cuales (arr i , arr j ) satisface la ecuación anterior de la línea son: (1, 2), (1, 5), (2, 3), (3, 4 ), (5, 3).
Entrada: m = 2, c = 1, arr[] = [ 1, 2, 3, 4, 2, 5 ]
Salida: 3 puntos ordenados
Método 1 (Fuerza bruta):
Genere todos los pares posibles (i, j) y verifique si un par ordenado particular (i, j) es tal que (arr i , arr j ) satisface la ecuación dada de la línea y = mx + c, y yo ≠ j. Si el punto es válido (un punto es válido si se cumple la condición anterior), incremente el contador que almacena el número total de puntos válidos.
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>
5
Complejidad de Tiempo: O(n 2 )
Espacio Auxiliar: O(1)
Método 2 (Eficiente):
dada la coordenada ax de un punto, para cada x hay un valor único de y y el valor de y no es más que m * x + c. Entonces, para cada coordenada x posible del arreglo arr, calcule cuántas veces el valor único de y que satisface la ecuación de la línea ocurre en ese arreglo. Almacene el recuento de todos los enteros de array, arr en un mapa. Ahora, para cada valor, arr i , agregue a la respuesta, el número de ocurrencias de m * arr i + c. Para un i dado, m * a[i] + c ocurre x veces en la array, luego, agregue x a nuestro contador para obtener el total de puntos válidos, pero debe verificar que si a[i] = m * a[i] + c entonces, es obvio que dado que esto ocurre x veces en la array, entonces una ocurrencia está en el i -ésimoLas ocurrencias de índice y resto (x – 1) son las coordenadas y válidas, así que agregue (x – 1) a nuestro contador de puntos.
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
5
Complejidad de tiempo : O(n)