All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 String Theory...not quite (Posted on 2010-07-27)
If the numbers 1 - 100 are written in one long string, how many substrings of minimum length 2 can be found with strictly decreasing numbers? e.g. 12345678910 has three such substrings: 91, 910, 10.

 No Solution Yet Submitted by Andre No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 computer solution | Comment 3 of 6 |

CLS
FOR i = 1 TO 100
s\$ = s\$ + LTRIM\$(STR\$(i))
NEXT
PRINT LEN(s\$), s\$

FOR i = 2 TO LEN(s\$)
IF MID\$(s\$, i, 1) < MID\$(s\$, i - 1, 1) THEN
IF lCt = 0 THEN
lCt = 2
ELSE
lCt = lCt + 1
END IF
ELSE
IF lCt > 0 THEN
PRINT MID\$(s\$, i - lCt, lCt); "  ";
totStr(lCt) = totStr(lCt) + 1
lCt = 0
END IF
END IF
NEXT
IF lCt > 0 THEN
PRINT MID\$(s\$, i - lCt, lCt); "  ";
totStr(lCt) = totStr(lCt) + 1
lCt = 0
END IF

PRINT : PRINT
FOR i = 0 TO 9
PRINT totStr(i);
NEXT
PRINT

finds substrings of various lengths without counting lower levels of substring (that is, a length-3 substring counts only as itself, and the two length-2's within it aren't counted).

What it finds are 65 of length 2 and 9 of length 3. But the length-3 substrings count for a total of three substrings each--the length-3 substring itself and two length-2 substrings.  So the total is 65 + 3*9 = 92.

With the above result completed, it's easier to retrofit an "analytic" solution:

`Length-3 strings:`
`At 9-10, 19-20, 29-30, ... , 99-100 (but with 89-90 excluded); so that's 10 - 1 = 9.`
`Length-2 strings not within length-3:`
`Teens: 12-13, ... , 18-19; Count: 720's: 23-24, ... , 28-29; Count: 6      21; Count 130's: 34-35, ... , 38-39; Count: 5      31, 32; Count 2...80's: 81, ... , 87; Count 790's: 90 (as 89-90 wasn't counted already), 91, ... , 98; Count 9.`

The teens through 80's count for 7 each, totalling 56. The nine from the 90's bring this to 65.

Then the 65 doubles and nine triples are combined as before: 65 + 3*9 = 92.

 Posted by Charlie on 2010-07-27 13:59:29

 Search: Search body:
Forums (0)
Random Problem
Site Statistics
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox: