4 ms·
That doesn’t satisfy the requirement “only do string processing and substitution on the numbers”. One can do this as follows (edit: spot the bug; this algorith
by Someone 7y ago
That doesn’t satisfy the requirement “only do string processing and substitution on the numbers”.
One can do this as follows (edit: spot the bug; this algorithm is broken, but can be easily fixed):
- Take the number as a string : "13565172345474789047"
- remove all 0s, 3s, 6s, and 9s: “155172454747847”
- replace all 4s and 7s by 1s : "155112151111811"
- replace all 5s and 8s by 2s : "122112121111211"
- sort the string’s characters : "111111111122222"
- replace all ‘111’ by ‘’ : "122222"
- replace all ‘222’ by ‘’ : "122"
- replace ’12’ by ’’ repeatedly: "2"
(you have to do this at most two times)
(proving that none of these steps changes the sum of the digits of the number (mod 3) is easy, as each step changes the sum by a multiple of 3)
⇒ that number is 2 (mod 3)