Loading collection data...
Collections are a way for you to organize kata so that you can create your own training routines. Every collection you create is public and automatically sharable with other warriors. After you have added a few kata to a collection you and others can train on the kata contained within the collection.
Get started now by creating a new collection.
This comment is hidden because it contains spoiler information about the solution
As mentioned in an earlier comment, you should explain the concept a bit better. At least the job of a
forerunner
must be explained.I added the boundaries for
k
ands
.An interesting kata!
Although I think it would be helpful to add a condition that
len(data)
is small and you should not dig into mathematicsFYI, my
$O(n\log p)$
solution passes in 6 to 9 seconds.Multiplication and division of large integers is not
$O(1)$
so your solution is not really linear. :)My linear solution times out. What is the expected time complexity?
Oops... hope I fixed that
In random test,
p
is not always a prime number.Thanks! Me like klutz)
Fixed it
What I meant is not flip the ref sol result with user sol in the assertion, because that will give
Expected <ref sol> to equal <user sol>
on error. That will be confusing for users of course.Run the ref sol first and put the ref sol result into a variable. And then, run the user sol and match it with the ref sol result variable.
The tests should run the ref sol first or copy the array first before executing user solution.
Fixed it
Thanks a lot for the comments!
Now the answer is searched modulo a prime number.
So I can remove restriction for
k < 30
and sift out the naive solution without volatile test.And now the implementation of the module is an significant part of this kata
Actual tests only go up to
2500000
. Since any solution must be at least linear it's just impossible to not time out with this constraint.(If you're reducing this constraint, you should turn
f
into an actual array too: an array of2500000
elements is certainly possible)Besides, the time taken for the tests are too volatile: even the author solution sometimes time out.
Loading more items...