4 ms·
Powers of two wouldn't work. If A = 2^1, B = 2^2 AA, B would evaluate to true. But you're right, the running times aren't any better, except that the constan
by ericd 16y ago
Powers of two wouldn't work.
If A = 2^1, B = 2^2
AA, B would evaluate to true.
But you're right, the running times aren't any better, except that the constant factors of dealing purely in arithmetic might make it faster in real terms if dealing with a lot of this type of thing than creating hash maps. If response time matters for the application (high frequency trading, etc), it might make a difference.
- StavrosK 16y agoSorry, by "powers of two" I meant bitmasks, not actually dividing with powers of two. Let A = 2^1, Z=2^26, and then OR with 2^1 when you encounter an A, etc. If the integer is non-zero when you're done, you've exhausted all the characters in the original string.
- ericd 16y agoAhh, sorry, good answer. Much simpler than finding an arbitrary number of primes.
- astrodust 16y agoThis is exactly what I was thinking and I have no idea why it didn't come up. Given an "alphabet" of 26 characters, that neatly fits inside a long int, and that's just crying out for a bitmask.