First collision point of two series
Given five numbers a, b, c, d and n (where a, b, c, d, n > 0). These values represent n terms of two series. The two series formed by these four numbers are b, b+a, b+2a….b+(n-1)a and d, d+c, d+2c, ….. d+(n-1)c
These two series will collide when at any single point summation values becomes exactly the same for both the series.Print the collision point.
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.
A naive approach is to calculate both the series in two different arrays, and then check for each element if it collides by running two nested loops
Time complexity: O(n * n)
Auxiliary Space: O(n)
An efficient Approach to the problem mentioned above is:
* Generate all elements of first series. Let current element be x.
* If x is also an element of second series, then following conditions should satisfy.
…..a) x should be greater than or equal to first element of second series.
…..a) Difference between x and first element should be divisible by c.
*If the above conditions are satisfied then the i-th value is the required meeting point.
Below is the implementation of the above problem :
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> |
Output :
82
Time Complexity: O(n)
Auxiliary Space: O(1)