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.
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
O(log min(m, n))(log min(m, n)) for gcd