# Minimum Multiple

# Minimum Multiple

paulpach + 1 comment I enjoyed this challenge. It took me a few days to come up with the right algorithm. In the process I learned to use mutable arrays in haskell, I learned a lot about lcm, gcd and module.

For all of you struggling: YES there is a solution that does not timeout in haskell.

My first try was the intuitive one: put all the values in an array, in every step either update the array or walk the array accumulating the lcm. This algorithm is O(1) for updates and O(n) for queries (assuming O(1) for lcm which is not true). This algorithm times out in several test cases.

My second try was to factorize the numbers and calculate the lcm by combining factorized numbers. The basic algorithm of storing the numbers an an array and either update them or calculate lcm of the range is the same. This algorithm is not faster than the previous one.

However, and this is a big tip: there is a way to do updates in O(log(n)) and queries in O(log(n)).

alistairtpotts + 0 comments Many thanks for the hint! I found this immensely fristrating right up until the point it became obvious.

nkrim + 0 comments Just completed this after around 2 weeks of attempts, I used @paulpach's hint and that jump-started me for sure, but, like many of you, I was still timing out.

Because there's so much going on behind the scenes in these functional languages (namely haskell as that's what I used), it's hard to tell what the actual slowing factor is, so to maybe help a few of you I'll give a tip.

The tip is: if you have a slow yet working solution following @paulpach's hint, then try and focus on simplifying your structures. Try and simplify things down until you have as much personal control as possible over operations on those structures. Optimizing the smaller operations as much as possible could mean the difference between 40 seconds and 4 seconds just by the fact that they're used so much during the longer test cases.

Hope this helps (and also hope this doesn't help too much that I spoiled it)

- MK
mkhotko + 0 comments Couild somebody tell how to speed up my code? It seems that calculating of least common multiple is slow =. I represent Array list of factorized on primes numbers, f.e.: {2,5,6,1,9} looks like

[[{2,1}], [{5,1}], [{2,1}, {3,1}], [], [{3,3}]]

Josenildo_Silva + 0 comments Anybody have resolved that problem in Haskell? What I do with limit for recursions?!

alex_lush + 0 comments Please, help me with my Erlang solution. I have no problems with test it locally but faced a permanent crash dump here. Thank you!

- XG
judejin + 2 comments my code can finish test case 9 in under 3 seconds on my own linux box... but timed out in the site... i have single threaded version timed out and multi-threaded version does not seem to help at all.... can you publish the expected run time with single thread and multi-thread on standard 4-core CPU?

- XG
judejin + 0 comments i'm using scala...

- JV
Jim10Asked to answer + 0 comments I've not yet tried to tackle Minimum Multiple myself.

I'm not sure how the site designers came up with the time-limit ranking for the different languages but Scala sure seems to be at a disadvantage. That's the language I'm using and I've got a few challenges that, no matter how clean and efficient I make it, simply will

**not**complete some testcase or another within the time limit. **sigh**I'll have a look at Minimum Multiple and, if I make any progress (big "if"), I'll let you know.

No more comments

Sort 6 Discussions, By:

Please Login in order to post a comment