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.
the input(n) is first converted to unary (1=1, 2=11, 3=111, ...)
first part (
^1?$
) and the ending$
check for n=0 or n=1in the second part, the regex uses basic divisor finding starting from 11(2 in decimal)
(11+?)
\1+
matches the previous group (initially 11) repeated one or more times in the unary representation of n. If at any point there is no match (the number is not divisible), the engine backtracks to make 11->111 (2->3 in decimal) and the process is repeated.e.g., even numbers (other than two) are pretty straightforward as they have an even number of ones (some multiple of
11
in unary, so the engine requires not backtracking)for odd numbers that are not prime, for example n=9(111111111),
(11+?)
matches 11 initially, but\1+
cannot match as there are 7 remaining ones. the engine backtracks and(11+?)
111 while\1+
takes care of the remaining onesfor odd numbers that are prime, for example n=11,
(11+?)
matches the initial 11, but\1+
cannot match the remaining 5 ones. engine backtracks, checking for 3,4,5,... and the regex will not match.Learnt it myself from here
How does this work?😁