# [eclipse-clp-users] Interesting problem from Google Code Jam

From: Sergey Dymchenko <kit1980_at_...6...>
Date: Tue, 31 May 2011 00:00:33 +0300
```Hi!

There is an interesting problem from Google Code Jam:
Essence of the problem: find minimum integer X such that Low <= X <=
High and for given list of integers L either L[i] divides X or X
divides L[i].
This is very hard problem because of the possible limits: 1 <= Low <=
High <= 10^16, size of L <= 10^4, each element of L <= 10^16.

I'm novice in constraint programming and here is my very naive solution:

:- lib(ic).

model(L, H, Notes, X) :-
X #>= L,
X #=< H,

(foreach(Y, Notes), param(X) do
max(X, Y) #= B * min(X, Y),
B #> 0).

solve(L, H, Notes, X) :-
model(L, H, Notes, X),
indomain(X),
writeln(X).

It will work fast for solve(8, 16, [1, 20, 5, 2], X), but 30 seconds
for solve(2, 1000000, [4, 1187, 310559, 3, 739, 7, 23, 19], X) and
till the end of time for solve(2, 10000000000000000, [4, 1187, 310559,
3, 739, 7, 23, 19], X).

Explanation and imperative solution for the problem can be found at