Short Problem Definition:
You will be given two arrays of integers and asked to determine all integers that satisfy the following two conditions:
 The elements of the first array are all factors of the integer being considered
 The integer being considered is a factor of all elements of the second array
Link
Complexity:
time complexity is O(A* (N+M))
space complexity is O(1)
Execution:
This challenge could also be solved using the Greatest Common Divisor. Given that the range of values is only [1,100], it is safe to assume that the naive solution will terminate within the time limit.
Solution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#!/bin/python import sys def isValid(a, b, candidate): for a_ele in a: if candidate % a_ele ! = 0 : return False for b_ele in b: if b_ele % candidate ! = 0 : return False return True n,m = raw_input ().strip().split( ' ' ) n,m = [ int (n), int (m)] a = map ( int , raw_input ().strip().split( ' ' )) b = map ( int , raw_input ().strip().split( ' ' )) cnt = 0 for candidate in xrange ( max (a), min (b) + 1 ): if isValid(a, b, candidate): cnt + = 1 print cnt 