We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Two Two
You are viewing a single comment's thread. Return to all comments →
Also some hints for people who are stuck: