1 Billion Users

We have N different apps with different user growth rates. At a given time t, measured in days, the number of users using an app is g^t (for simplicity we'll allow fractional users), where g is the growth rate for that app. These apps will all be launched at the same time and no user ever uses more than one of the apps. We want to know how many total users there are when you add together the number of users from each app.
After how many full days will we have 1 billion total users across the N apps?

Signature

int getBillionUsersDay(float[] growthRates)

Input

1.0 < growthRate < 2.0 for all growth rates
1 <= N <= 1,000

Output

Return the number of full days it will take before we have a total of 1 billion users across all N apps.

Examples

Example 1
growthRates = [1.5]
output = 52

Example 2
growthRates = [1.1, 1.2, 1.3]
output = 79

Example 3
growthRates = [1.01, 1.02]
output = 1047

Solution

There's already a post about this question here on LeetCode, but not only the answers in the comments are not explained, but I think the time complexities are wrong.

Here I'll explain how I understand the solution for this problem.

First we can think of a brute force approach by trying any day, adding all rates, and if the total users is less than a billion we'd try again with one more day, and so on.
We can start with 1 day, but we don't know the maximum possible number of days for the current apps (the input array), so we'd have to loop indefinitely until we find the first number of days that sums a billion users.

Remember that the days are not cumulative, so the process is easier as we don't need to store users for previous days as we increment them.

So we're checking every day up to the target, t. This takes O(t) time.
Then we're calculating u = g^t for every growth rate. This takes O(n) time, and this is done for each day, giving a total of O(nt) time.

For each day, we can break when the sum of users passes a billion before iterating all the apps to "optimize" some cases, but the worst case is still O(nt).

Using only the maximum rate of the array doesn't work in all cases, and I think this is expected to come up with during the interview, especially for edge cases like arr2 below which is easier to see than arr1:

Consider arr1 = [1.01, 1.0101, 1.0102]. The sum of users of the 2 smallest rates takes less days than the the greatest.
We can visualize this with a plot. The x axis represents the number of days, and the y the users.
You can see that the blue line (the sum of the 2 smallest) will reach a billion before the red line (the greatest rate).
This can also be proved by doing the calculations (once you have a correct algorithm):
The answer for arr1 is 1951 days.
The formula to get the number of days to reach a billion users is t = log_g(u) where the rate g is the base of the logarithm.
The result of log_1.0102(10**9) is 2042.0368.
Therefore the correct solution is not the days for the maximum rate.

Of course you won't be able to plot during the interview. The intuition to detect these cases is that if the differences between the growth rates is very very small (a lot of decimal places) then the "greatest" rate would be greater just by an almost insignificant factor, so the sum of the rest of the rates could surpass it.

Also consider arr2 = [1.9, ..., 1.9] where n = 1000. All rates are the greatest, and because they all contribute to the total users, it would take less days than a single 1.9.
See this plot and see how the lines scale.
Prove with the formulas as well:
log_1.9(10**9) = 32.2865
Run the algorithm on arr2 and the solution is 22, again less than the number for the greatest, or in this case, only one of the greatest.

The intuition here is that if the greatest rate is repeated in the array, then obviously it would take you less days to reach a billion users because the sum of all the greatest would yield more users than only one of them.

BILLION = 10 ** 9

def getBillionUsersDay_brute(growthRates):
    '''
    Time O(nt)
    
    Space O(1)
    '''
    days = 0
    users = 0
    # O(nt)
    while users < BILLION:
        days += 1
        users = 0
        # O(n)
        for app in growthRates:
            users += app ** days
            if users >= BILLION:
                break
    
    return days

Can we do better? We'd have to reduce the runtime to one of the following: O(n + t), O(n log t), or O(t log n).

To reach O(n + t), we'd need to process the array once then loop through the days, or viceversa. The core challenge of this problem is searching for t, and t depends on the sum
of the growth rates. I can't think of how to do that and only iterating each sequence once.

To reduce one of the variables to a logarithmic scale, remember that this is a searching problem. We're essentially doing a search for days from 1 to t, in increasing order, sequentially checking one by one, in O(t) time.
We can use binary search here, because the days are "sorted", and reduce this step to O(log t).
Now to use binary search we need to know where to start and where to finish. We were already starting the search at day 1, but we don't know t, which would be the ideal upper bound.

The intuition to get a valid upper bound without knowing t is that when the greatest rate alone yields a billion users, more days would always yield more than a billion users, so less days could yield less users, depending on the input.
This means that we can use the maximum rate in the array to calculate the days it'd take to reach a billion and use this value as the upper bound for the binary search.
This value could be different from t, depending on the input, so the runtime is actually O(log m) where m is the number days for the greatest rate using the formula t = log_g(u). This is a decimal number so we have to round up this value.
However, I think that if t and m are different, they wouldn't differ by a lot. I'd say they're approximately equal, but I don't know how to mathematically prove this. But anyways, t <= m, so the worst case is still O(log m).
And for each day in the binary search, we'd sum all the rates in O(n) time, giving a total worst case time complexity of O(n log m).

import math


def getBillionUsersDay(growthRates):
    '''
    Time O(n log m)
    
    Space O(1)
    '''
    # O(n)
    max_rate = max(growthRates)
    # upper bound
    max_days = math.ceil(math.log(BILLION, max_rate))

    l = 1
    r = max_days
    # O(n log m)
    while l <= r:
        mid = (r + l) // 2

        users = 0
        # O(n)
        for g in growthRates:
            users += g ** mid
            if users >= BILLION:
                break

        if users < BILLION:
            l = mid + 1
        else:
            r = mid - 1

    return mid