# CodeWars Kata -- Twice Linear

## Sep 29, 2016 20:52 · 337 words · 2 minute read Python Codewars

CodeWars Kata —— Twice Linear

Description:

Consider a sequence `u` where u is defined as follows:

1. The number `u(0) = 1` is the first one in `u`.
2. For each `x` in `u`, then `y = 2 * x + 1` and `z = 3 * x + 1` must be in `u` too.
3. There are no other numbers in `u`.

Ex: `u = [1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27, ...]`

1 gives 3 and 4, then 3 gives 7 and 10, 4 gives 9 and 13, then 7 gives 15 and 22 and so on…

Given parameter `n` the function `dbl_linear` (or dblLinear…) returns the element `u(n)` of the ordered (with <) sequence `u`.

Example:

`dbl_linear(10) should return 22`

Note:

Focus attention on efficiency

This kata is only `5kyu` however costs me days.

My finnal solution:

``````def dbl_linear(n):
u = 

def isInU(q):
low = 0
high = len(u)-1
while low <= high:
mid = int((low+high)/2)
if u[mid] == q: return True
if u[mid] > q: high = mid-1
else: low = mid+1
if q > u[mid]: return False, mid + 1
elif q < u[mid]: return False, mid
else: print('sth. wrong')

for index, num in enumerate(u):
jx = isInU(2*num+1)
if jx != True:
u.insert(jx, 2*num+1)
jy = isInU(3*num+1)
if jy != True:
u.insert(jy, 3*num+1)
if index == int(n*3/5):
break

return u[n]
``````

The key point was that `3/5`。Be more that `3/5` will only result in Timeout. But this number was only gained through tests but not provements. It is a shame.

The author of this kata provide a solution from which I learned a lot.

``````from collections import deque

def dbl_linear(n):
h = 1; cnt = 0; q2, q3 = deque([]), deque([])
while True:
if (cnt >= n):
return h
q2.append(2 * h + 1)
q3.append(3 * h + 1)
h = min(q2, q3)
if h == q2: h = q2.popleft()
if h == q3: h = q3.popleft()
cnt += 1
``````

Two `deques` guarantee that `h` comes out in order.