This is a question I had as an exercise.
There are two types of bacteria. Say x and y. Every second they multiply while changing their type.
Type x becomes 2 y type and 1 x type (x -> 2y + x). Type y becomes 3 x type and 1 y type (y -> 3x + y). Other than that, 1 x type and 3 y type are born spontaneously (each second -> x + 3y).
The task is to calculate the number of bacteria after a given time t.
I wrote a code here:
x = 1
y = 1
t = 2
def calcFinalBacteria (x, y, t):
for i in xrange (t):
tempX = x + y * 3 # contribution by x bacteria (1) and y bacteria (3)
tempY = x * 2 + y # contribution by x bacteria (2) and y bacteria (1)
x += tempX + 1 - x # spontaneous addition of 1 x bacteria
y += tempY + 3 - y # spontaneous addition of 3 y bacteria
print x, y
calcFinalBacteria (x, y)
The time complexity of my code is O(t) here. But is there any way for improvement? For small inputs it is okay. But when I push t up to 10^18 and increase x, y up to 1000, it takes much time to find out
So if I'm understanding this right, x' = x+3y+1 and y' = 2x+y+3. Suppose your initial population is ten x and seven y, and you want to evolve it by one step. This can be modeled with the following matrix multiplication:
|1 3 1| |10|
|3 1 3| x | 7|
|0 0 1| | 1|
So to find the answer, you need to repeat the matrix multiplication t times.
Although, the way you've written the code, each x turns into 2y and 0 x, not 2y and one x.