PROBLEM LINK:
Author: Himanshu
DIFFICULTY:
EASY
PREREQUISITES:
Modular Exponentiation, Arithmetic progression
PROBLEM:
Given two AP’s in which the first element of both the AP’s are the same. You need to find the number of common elements between these two given AP’s.
EXPLANATION:
Since the first element of both the arrays is the same. Let it be a.
common difference of first array = m
common difference of second array = n
general term for first AP:- a + x * m , where 0 <= x <= (p-1)
general term for second AP:- a + x * n , where 0 <= x <= (q-1)
The common elements will themselves form an AP. The common difference for the new AP will be the lcm of the common differences of the given two APs.
d = lcm(m, n)
Now the last term of this AP will be less than or equal to the min of the last terms of the two given APs.
x = min(last term of arr, last term of brr)
Now you need to find no. of common terms say N
a +(N-1)*d <= x
Solve the above equation to find N
COMPLEXITY:
O(log min(m, n))(log min(m, n)) for gcd