multiplying two int arrays in python

Question

I am trying to retrieve the answer for multiplying two int arrays (output is also an int array).

For example, num1 = [2, 2, 0], num2 = [1, 0] will give us [2, 2, 0, 0]

What I tried was

def multiply(num1, num2):
    if num1 == [0] or num2 == [0]:
        return [0]
    sign = -1 if (num1[0] < 0) ^ (num2[0] < 0) else 1
    num1[0] = abs(num1[0])
    num2[0] = abs(num2[0])
    res = [0] * (len(num1) + len(num2) + 1) # space O(n + m)
    for i in range(len(num1) - 1, -1, -1):
        for j in range(len(num2) - 1, -1, -1):
            res[i + j + 1] += num1[i] * num2[j]
            res[i + j] += res[i + j + 1] // 10
            res[i + j + 1] %= 10
    res[0] *= sign

    return res

trying to imitate the grade-school multiplication.

However, in the official answer to this question, it adds these two lines to remove the leading zeros.

res = res[next((i for i, x in enumerate(res) if x != 0), len(res)):] or [0]
return res

I am so confused about how it works. It seems like it is just retrieving the indices of an array where the value is not 0, but I don't understand how next works with that. Also, is there a simpler way to do what it actually tries to do?

Answer 1

Explanation

res = res[next((i for i, x in enumerate(res) if x != 0), len(res)):] or [0]
return res

In short: this gives the index of the first non-zero and slices the list from there.

• or [0] if given empty input this will result in returning [0]
• res[index:] this will return everything from given index onwards
• next(iterable, something2) get next value from iterable, return something2 if iterable is empty. this makes sure that if a list of 0's is given, this will give the last index of the array
• (i for i, x in enumerate(res) if x != 0) this is a generator creating a stream of values of all indices (i) of values (x) in the list that are not zero. The values (x) are not returned, only the indices (i).

The generator will not yield results for 0's, making sure the first thing next() can use is the first index of a nonzero. Passing back that value to the slice.

Another solution

Why not turn them to numbers, multiply and then convert back to list? Faster & more readable

def to_int(list_int):
    # This can also be done with list comprehension and powers of 10
    return int("".join(map(str, list_int)))

def to_list(integer):
    return [int(x) for x in str(integer)]


num1 = [2, 2, 0]
num2 = [1, 0]

to_list(to_int(num1) * to_int(num2))

[2, 2, 0, 0]

Performance

Comparing to the given multiply()

%timeit multiply(num1, num2)
3.87 µs ± 44.5 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

%timeit to_list(to_int(num1) * to_int(num2))
2.74 µs ± 25.4 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

Answer 2

Yes, this is a pretty obscure one-liner to accomplish stripping the leading zeros. Let's break it down by simplifying different parts.

If you remove everything within the next call you can see it's just returning a single int index to slice the result with. If that returns an empty array, then the answer is [0].

res = res[next(...):] or [0] 

Now let's break down the statement inside of next before we talk about next.

(i for i, x in enumerate(res) if x != 0), len(res)

This statement is a tuple, whose first value is a generator that generates the index is where the value x is not 0. The second value is the length of res.

There's an obscure trick here with next - if the generator that is the first value in the tuple is not empty, then next will return the first value from that generator which is the first index that is not a zero. If it is empty however (i.e. all digits are 0), it will return the second value len(res). This result is then fed into the slice operator to remove all of the zeros - either by slicing up to the first non-zero index or slicing away the entire array.

This to me seems very convoluted. The readable pythonic way from my perspective is simply:

while len(res) > 1 and res[0] == 0:
    res.pop(0)
return res

Answer 3

(i for i, x in enumerate(res) if x != 0)

this returns a generator with indices of array where the number is not equal to 0. So in this array:

number = [0, 0, 4, 9]

your code inside next (i for i, x in enumerate(res) if x != 0) will give a generator which has the values

[2, 3]

2 here is an index and refers to the 4 in the array "number" and similarly 3 here refers to 9 in the original number. and all next does is, it fetches the next value from the generator each time it is called on a generator. calling it once and for the first time return 2 from this result. which is the index of the first non 0 element from the original number.

and then we just slice the array from this index of the first non zero number to the complete length of the original array.

res[2:] this syntax is called slicing where 2 specifies the starting index and no value after colon signifies the enter rest of the array.