Hi!

Maybe Kaveh could use a Monte Carlo-type test - i.e. pick a fixed number of

randomly chosen k's to test and look

whether the respective difference exists. This can be done in O( min(m,n) *

iterationCount)

[assuming you can check in O(1) whether a given number belongs to a set].

Furthermore if there are at least two solutions to a given k, return false.

Another simple tests that may speed up the process is to check first whether

min_element(A) < max_element(B)

If this holds return false, since one can construct a negative number thus

missing at least one number from [0,mn-1].

Runtime: O(max(m,n))

I have constructed some covering sets - there aren't that many (if you bound

the members of the set to be in [0,mn-1]!).

So unless explicitly constructed it is very unlikely that two sets have the

desired property

[exponentially small in the number of iterations - if you choose each set

member uniformly at random].

HTH,

Ronny