- Practice
- Algorithms
- Strings
- Two Two
- Discussions

# Two Two

# Two Two

gnawer + 0 comments So, for people who are stuck:

This problem is very confusingly formulated. What it wants from you is, given a string, find all substrings that represent powers of 2.

There are powers up to 800, that's a 800-bit integer, you ain't going to find one in any language. Hint: use strings.

Then, you're going to need to find lots of substrings in a string. Others mentioned Aho-Corasick. I managed to do it just with tries. Aho-Corasick is essentially tries plus some optimization. So same thing, but simpler.

jacomatic + 0 comments this question is word soup.

alatas + 0 comments Don't forget the 2^0 :)

Inferno285 + 0 comments For what It's worth I solved this using javascript first and then tested with python3. It timedout in python3 but it did work just fine using pypy3. After creating a trie I iteratively searched starting at the back of the string and only if the number is 2, 4, 6, or 8. I haven't seen any comments suggesting such an efficient algorithm.

CodierMaschine + 0 comments Also some hints for people who are stuck:

- Basically we are talking about a state machine that can match substrings, e.g. which recognizes that when you see a '1', this could be the start of 1, 16, 128, 1024, ..., and which knows at every step moving further along the string what to do (e.g. increase the count, or drop to follow the sequence if we just saw a digit that is not part of any "power of two" sequence, such as with '1025', where the '5' makes it not a "power of two" for x < 16 [I have no idea whether it is the beginning of a power of two up to x = 800])
- You can surely represent this as a trie
- For the compiler writers among you: I used a non-deterministic finite state machine (with 94318 states) - it is probably not worth the effort to create a deterministic one
- To find out more about such state machines, check out the classic "Aho, Sethi, Ullman - Compilers" book

Sort 67 Discussions, By:

Please Login in order to post a comment