We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Very nice! Without the parallelization, Test Case #1 can time out. I think there's a handful of similar interesting observations about speed.
- The arrays can be skipped, since the GCD and LCM can be calculated on the fly. Streams can still be used, just by feeding the integers into the stream directly, no?
- It seems worth testing that the intermediate LCMs are still <= 100, because in that case the algorithm can terminate early. Especially since if there's more than one distinct prime factor > 7 among the A_n's, the LCM will definitely be over one hundred.
- Ditto for testing that the GCD isn't smaller than the LCM.
- Finally, finding the number of values that are in between A and B is equivalent to finding out how many factors there are for GCD_b/LCM_a. And for that, at worst we only need to test 2 thru 10 as divisors. Pretty cheap!
I wonder if there's an efficient way to calculate the LCM of a set of numbers, without finding the intermediate LCMs along the way. Feels like there's some redundant calculations going on.
Thanks for indulging the musings, cheers!
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Between Two Sets
You are viewing a single comment's thread. Return to all comments →
Very nice! Without the parallelization, Test Case #1 can time out. I think there's a handful of similar interesting observations about speed.
- The arrays can be skipped, since the GCD and LCM can be calculated on the fly. Streams can still be used, just by feeding the integers into the stream directly, no?
- It seems worth testing that the intermediate LCMs are still <= 100, because in that case the algorithm can terminate early. Especially since if there's more than one distinct prime factor > 7 among the A_n's, the LCM will definitely be over one hundred.
- Ditto for testing that the GCD isn't smaller than the LCM.
- Finally, finding the number of values that are in between A and B is equivalent to finding out how many factors there are for
GCD_b/LCM_a
. And for that, at worst we only need to test 2 thru 10 as divisors. Pretty cheap!I wonder if there's an efficient way to calculate the LCM of a set of numbers, without finding the intermediate LCMs along the way. Feels like there's some redundant calculations going on.
Thanks for indulging the musings, cheers!