Dados cinco números a, b, c, d y n (donde a, b, c, d, n > 0). Estos valores representan n términos de dos series. Las dos series formadas por estos cuatro números son b, b+a, b+2a….b+(n-1)a y d, d+c, d+2c, ….. d+(n-1)c
Estos dos la serie colisionará cuando en cualquier punto único los valores de suma sean exactamente iguales para ambas series. Imprima el punto de colisión.
Example:
Input : a = 20, b = 2,
c = 9, d = 19,
n = 100
Output: 82
Explanation:
Series1 = (2, 22, 42, 62, 82, 102...)
Series2 = (28, 37, 46, 55, 64, 73, 82, 91..)
So the first collision point is 82.
Un enfoque ingenuo es calcular ambas series en dos arrays diferentes y luego verificar si cada elemento colisiona ejecutando dos bucles anidados
Complejidad del tiempo : O(n * n)
Espacio auxiliar : O(n)
Un enfoque eficiente del problema mencionado anteriormente es:
* Generar todos los elementos de la primera serie. Sea x el elemento actual.
* Si x es también un elemento de la segunda serie, entonces las siguientes condiciones deben cumplirse.
…..a) x debe ser mayor o igual que el primer elemento de la segunda serie.
…..a) La diferencia entre x y el primer elemento debe ser divisible por c.
*Si se cumplen las condiciones anteriores, entonces el valor i-ésimo es el punto de encuentro requerido.
A continuación se muestra la implementación del problema anterior:
C++
// CPP program to calculate the colliding
// point of two series
#include<bits/stdc++.h>
using namespace std;
void point(int a, int b, int c, int d, int n)
{
int x , flag = 0;
// Iterating through n terms of the
// first series
for (int i = 0; i < n; i++)
{
// x is i-th term of first series
x = b + i * a;
// d is first element of second
// series and c is common difference
// for second series.
if ((x - d) % c == 0 and x - d >= 0)
{
cout << x << endl ;
flag = 1;
break;
}
}
// If no term of first series is found
if(flag == 0)
{
cout << "No collision point" << endl;
}
}
// Driver function
int main()
{
int a = 20 ;
int b = 2 ;
int c = 9;
int d = 19;
int n = 20;
point(a, b, c, d, n);
return 0;
}
// This code is contributed by 'saloni1297'.
Java
// Java program to calculate the colliding
// point of two series
import java.io.*;
class GFG
{
static void point(int a, int b, int c, int d, int n)
{
int x , flag = 0;
// Iterating through n terms of the
// first series
for (int i = 0; i < n; i++)
{
// x is i-th term of first series
x = b + i * a;
// d is first element of second
// series and c is common difference
// for second series.
if ((x - d) % c == 0 && x - d >= 0)
{
System.out.println( x ) ;
flag = 1;
break;
}
}
// If no term of first series is found
if(flag == 0)
{
System.out.println ("No collision point");
}
}
// Driver function
public static void main (String[] args)
{
int a = 20 ;
int b = 2 ;
int c = 9;
int d = 19;
int n = 20;
point(a, b, c, d, n);
}
}
// This code is contributed by vt_m
Python
# Function to calculate the colliding point # of two series def point(a, b, c, d, n): # Iterating through n terms of the # first series for i in range(n): # x is i-th term of first series x = b + i*a # d is first element of second # series and c is common difference # for second series. if (x-d)%c == 0 and x-d >= 0: print x return # If no term of first series is found else: print "No collision point" # Driver code a = 20 b = 2 c = 9 d = 19 n = 20 point(a, b, c, d, n)
C#
// C# program to calculate the colliding
// point of two series
using System;
class GFG {
static void point(int a, int b, int c,
int d, int n)
{
int x, flag = 0;
// Iterating through n terms of the
// first series
for (int i = 0; i < n; i++) {
// x is i-th term of first series
x = b + i * a;
// d is first element of second
// series and c is common difference
// for second series.
if ((x - d) % c == 0 && x - d >= 0) {
Console.WriteLine(x);
flag = 1;
break;
}
}
// If no term of first series is found
if (flag == 0) {
Console.WriteLine("No collision point");
}
}
// Driver function
public static void Main()
{
int a = 20;
int b = 2;
int c = 9;
int d = 19;
int n = 20;
point(a, b, c, d, n);
}
}
// This code is contributed by vt_m
PHP
<?php
// PHP program to calculate
// the colliding point of
// two series
function point($a, $b, $c, $d, $n)
{
$x ; $flag = 0;
// Iterating through
// n terms of the
// first series
for ($i = 0; $i < $n; $i++)
{
// x is i-th term
// of first series
$x = $b + $i * $a;
// d is first element of
// second series and c is
// common difference for
// second series.
if (($x - $d) % $c == 0 and
$x - $d >= 0)
{
echo $x;
$flag = 1;
break;
}
}
// If no term of first
// series is found
if($flag == 0)
{
echo "No collision po$";
}
}
// Driver Code
$a = 20 ;
$b = 2 ;
$c = 9;
$d = 19;
$n = 20;
point($a, $b, $c, $d, $n);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript program to calculate
// the colliding point of
// two series
function point(a, b, c, d, n)
{
let x ;
let flag = 0;
// Iterating through
// n terms of the
// first series
for (let i = 0; i < n; i++)
{
// x is i-th term
// of first series
x = b + i * a;
// d is first element of
// second series and c is
// common difference for
// second series.
if ((x - d) % c == 0 &&
x - d >= 0)
{
document.write(x);
flag = 1;
break;
}
}
// If no term of first
// series is found
if(flag == 0)
{
document.write("No collision po");
}
}
// Driver Code
let a = 20 ;
let b = 2 ;
let c = 9;
let d = 19;
let n = 20;
point(a, b, c, d, n);
// This code is contributed by _saurabh_jaiswal.
</script>
Producción :
82
Complejidad de tiempo: O(n)
Espacio auxiliar: O(1)
Este artículo es una contribución de Twinkle Bajaj . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA