Replace 0 with 01 and 1 with 10 in a List[int]

I am taking efforts to solve problem K-th Symbol in Grammar - LeetCode

On the first row, we write a `0`. Now in every subsequent row, we look at the previous row and replace each occurrence of `0` with `01`, and each occurrence of `1` with `10`.

``````Explanation:
row 1: 0
row 2: 01
row 3: 0110
row 4: 01101001
``````

I wrote such a replace function

``````        def replace(row: "List[int]") -> "List[int]":
"""
rtype: row
"""
for i in range(len(row)):
if row[i] == 0: #0 -> 01
row.insert(i+1, 1)
elif row[i] == 1: #1 -> 10
row.insert(i+1, 0)
return row
``````

However, it does not work properly.

``````In : r2 = replace()
In : r2
Out: [0, 1]
In : r3 = replace(r2); print(r3)
[0, 1, 0, 1] # correct is [0, 1, 1, 0]
In : r4 = replace(r3); print(r4)
[0, 1, 0, 1, 0, 1, 0, 1] #correct is  ['0', '1', '1', '0', '1', '0', '0', '1']
``````

Use a new list does not work either.

``````    def replace(row: "List[int]") -> "List[int]":
"""
rtype: row
"""
copy = list(row)
for i in range(len(copy)):
if copy[i] == 0: #0 -> 01
row.insert(i+1, 1)
elif copy[i] == 1: #1 -> 10
row.insert(i+1, 0)
return row
``````

What's the problem?

• provide expected output – AkshayNevrekar Apr 18 at 8:26
• You use slice locations from the list while adding objects. That doesn't work. – Stef van der Zon Apr 18 at 8:30
• you are iterating over your list at the same time you are modifying it. Use another list to write the result in `replace` – pLOPeGG Apr 18 at 8:31
• Use another list does not help, Lante provide a index shifter solution below. @pLOPeGG – Jon Apr 18 at 8:43
• @Jon see my answer, you did not use properly the other list. – pLOPeGG Apr 18 at 8:50

the problem with your code is that you are inserting elements in a list in a loop without taking into account the elongation of the list.

This can be solved by adding a simple "index shifter":

``````def replace(row: "List[int]") -> "List[int]":
for en, i in enumerate(range(len(row))):
if row[i] == 0: #0 -> 01
row.insert(i+1 + en, 1)
elif row[i] == 1: #1 -> 10
row.insert(i+1 + en, 0)
return row

replace([0, 1, 1, 0])

>>> [0, 1, 1, 0, 1, 0, 0, 1]
``````

Some explanation:

I gave this answer because you asked what was wrong with your code, and I supposed you wanted to, or you were asked to, solve this task with this approach.

I have to say I'd definitely go with other approaches, as many have proposed, anyway:

• if you really want to understand why it works print `row` and `row[i]` in the for loop
• you'll probably find out that this approach works only for this specific task of the "k-th symbol" (try for example `replace([0, 0])`), and this is quite mind blowing
• p.s. if you were wondering about the `en` variable, here it is used just for "didactic" purposes, as in this case it's always `en == i >>> True`

Update:

Given row N and index K, return the K-th indexed symbol in row N. (The values of K are 1-indexed).

with:

``````row 1: 0
row 2: 01
row 3: 0110
row 4: 01101001
# etc.
``````

and the following constraints:

N will be an integer in the range [1, 30]

K will be an integer in the range [1, 2^(N-1)]

so, I think none of the proposed solutions is going to work with a list of 2^29 elements.
In order to solve the quiz, we have to go a bit deeper.

Basically, what we are doing by replacing `0` and `1` with `01`, `10`, starting from `0`, at an `n-th` iteration, is extending list from `n-1-th` with the the same inverted list, in fact:

``````def replace(row):
return row + list(map(lambda x: int(not x), row))

replace([0, 1, 1, 0])

>>> [0, 1, 1, 0, 1, 0, 0, 1]
``````

produces the correct output, and that's why your corrected algorithm works.

But still this wouldn't allow you to deal with a `N = 2^30` constraint. As hinted in the link, a recursive approach is the best.
Here I give a possible solution with no explanation, just as a curiosity:

``````def solution(n, k):
if n == 1:
return 0
if k <= 2**(n-1)/2:
return solution(n-1, k)
else:
return 1 - solution(n-1, k-2**(n-1)/2)

``````

`

Use `str.join` with `dict`:

``````a = '0'
d = {'0': '01', '1': '10'}
# Now run below line only
a = ''.join(d[s] for s in a)
a
``````

Output:

``````01
0110
01101001
...
``````

Just as an explanation of how to use another list to write a result while iterating over a list:

``````def replace(row: "List[int]") -> "List[int]":
ret = []
for i in range(len(row)):
if row[i] == 0: #0 -> 01
ret += [0, 1]
elif row[i] == 1: #1 -> 10
ret += [1, 0]
return ret
``````

You shouldn't modify a iterable while iterating over unless you want to take into account length changes. Most of the time it is easier to create anothe list and fill it little by little. And the result is:

``````replace([0,1,1,0])
>>> [0, 1, 1, 0, 1, 0, 0, 1]
``````
``````def replace(row: "List[int]") -> "List[int]":
"""
rtype: row
"""
outList = []
for val in row:
if val == 0: #0 -> 01
outList.append(0)
outList.append(1)
elif val == 1: #1 -> 10
outList.append(1)
outList.append(0)
return outList
``````

Your version modified the list as it read it. Its range was only the length of the original array. It only looked at two values, but it inserted a 1 after the first 0. It then saw the 1, causing it to insert another 0.