Teaching Kids Programming: Videos on Data Structures and Algorithms
Previously, we know there are 45 continuously increasing digits (each digit is 1 plus its previous digit) such as 12, 23, 12345. This can actually be computed via Math Combination.
The numbers are actually the sublists of “123456789” and thus we have C(9, 2) to pick a left index and right index. Also we have C(9, 1) to pick a single digit, and thus:
The C(N, M) function is a combination that represents the number of ways of picking M out of N. And it is equal to:
In particular, when M is two:
And thus the number of sublists for a N-length string is:
Thus, usually if we want to bruteforce all sublists – the time complexity is 
We can use the following Python code to add up to the number of sublists:
1 2 3 4 5 6 7 | def f(n): s = 0 c = 0 for i in range(n): c += 1 s += c return s |
def f(n):
s = 0
c = 0
for i in range(n):
c += 1
s += c
return sThe first few numbers are: 1, 3, 6, 10, 15, 21, 28.
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Teaching Kids Programming - Contiguously Increasing Numbers (Depth First Search and Breadth First Search Algorithm)
Next Post: Teaching Kids Programming - Python Function to Find the Mode in an Array (Most Frequent Number)
