Ad
  • Custom User Avatar

    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=1

    in 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 ones

    for 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

  • Custom User Avatar

    How does this work?😁