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
time complexity is O(A* (N+M))
space complexity is O(1)
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.
#!/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
If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.