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>
Producción :
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
Producción:
5
Complejidad de tiempo : O(n)