Teaching Kids Programming – Another Birthday Candles Problem (Binary Search and Brute Force / Linear Search)

Teaching Kids Programming: Videos on Data Structures and Algorithms

Another Birthday Candles Problem

Unlike the Original Birthday Candles Problem described here: Teaching Kids Programming – The Birthday Candles Problem (Three Algorithms), the number of candles blown for year N is the number of digits of integer N. For example, from year 1 to year 9, a candle is blown for each year, and on year 10 to 99, two candles are blown for each year and so on. Given total candles blown T, we want to figure out the number of years from year 1 to N so that the sum of all the candles blown is T.

The math problem can be formulated as the following:

Given g(i) is the number of candles blown for the year, which is the number of the digits,
We want to find out the integer N if there is, such as:

The number of digits for a integer i (the g(i) function) can be computed as:

method 1, converting integer to string and we can get the length.

1
2

def g(i):
    return len(str(i))

def g(i):
    return len(str(i))

method 2, use the log function:

1
2

def g(i):
    return int(math.log10(i)) + 1

def g(i):
    return int(math.log10(i)) + 1

The accumulated sum G(i) from integer 1 to i inclusive can be done via bruteforce:

1
2

def G(N):
    return sum(g(i) for i in range(1, N + 1)

def G(N):
    return sum(g(i) for i in range(1, N + 1)

However, a better solution would be to do the counting, please see the algorithms here: Algorithms to Compute the Sum of the Number of Digits for First N Natural Integers

The Bruteforce Algorithm

We can try the year from 1 until we get the target sum T or the sum is exceeding it:

1
2
3
4
5
6
7

def f(T):
    s = 0
    i = 0
    while i <= T:
        i += 1
        s += g(i)
    return i if s == T else -1

def f(T):
    s = 0
    i = 0
    while i <= T:
        i += 1
        s += g(i)
    return i if s == T else -1

The time complexity is O(Tg) and the space complexity is O(1).

The Binary Search Algorithm

Of course, we can binary search since the search space is monotone increasing e.g. when N increases, G(N) increases.

1
2
3
4
5
6
7
8
9
10
11
12
13

def f(T):
    L = 1
    R = T
    while L <= R:
        M = L + R >> 1
        s = G(M)
        if s == T:
            return M
        elif s < T:
            L = M + 1
        else:
            R = M - 1
    return -1

def f(T):
    L = 1
    R = T
    while L <= R:
        M = L + R >> 1
        s = G(M)
        if s == T:
            return M
        elif s < T:
            L = M + 1
        else:
            R = M - 1
    return -1

The time complexity is O(log(T)g) and the space complexity is O(1).

–EOF (The Ultimate Computing & Technology Blog) —