Finding Digit Strings In Powers Of Two
September 24, 2013
[ I told you in a previous exercise that I was having internet connectivity issues at home. It took three weeks, but a repairman from the local telephone company finally found that, during repairs on the soffit underneath my roof overhang, the roofer nailed through a board with a nail that was too long, so it penetrated the board and the telephone cable that was nailed to the other side of the board. As the temperature and humidity changed during the day, sometimes the nail made contact with two ends of the same conductor, and everything worked properly, but sometimes the nail made contact with two different conductors, causing a short circuit and preventing the telephone from working. At the same time, my wifi router developed some kind of internal problem, also intermittent. I have now replaced both the wire and the router and everything seems to be working. The problems were hard to solve because both of them were intermittent. ]
Today’s problem comes from one or another of the competitive programming sites, I’m not sure which:
Search every power of two below 210000 and return the index of the first power of two in which a target string appears. For instance, if the target is 42, the correct answer is 19 because 219 = 524288, in which the target 42 appears as the third and fourth digits, and no smaller power of two contains the string 42.
Your task is to write the search program described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Pages: 1 2