5

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?

Improve this question
2
  • 3
    how does [2, 2, 0] * [1, 0] become [2, 2, 0, 0] ? Commented Aug 21, 2019 at 7:09
  • 1
    it denotes 220 * 10 = 2200 Commented Aug 21, 2019 at 7:13

4 Answers 4

Reset to default
5

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)
Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

forgot to mention that this is an interview practice, so that would not be the best time and space complexity
this is from a study book, so it's just a practice. My question shows the official answer, but I just don't understand the answer.
If you care about code readability at all or expect anybody else to ever work on your code, the alternative solution is definitely the way to go. I really wouldn't want to code with someone who uses your textbook answer in real code.
3

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
Improve this answer

1 Comment

Thanks, it makes sense! Do you know why the number of digits required for the product is at most n + m for n and m digit operands? It seems like this is the cause of leading 0 in the resulting array.
2

(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.

Improve this answer

Comments

1

The first argument to that next is a generator expression, which is like a list comprehension except that it makes a generator instead of a list. It's a roundabout way to find the index of the first nonzero element of the old res, because the next here just finds the first value generated by the generator, and discards the rest.

I do enjoy a slick one-liner once in a while, but in this case I'd probably just write the loop explicitly.

for i in range(len(res)):
    if res[i]:
        res = res[i:]
        break
else:
    res = [0]
return res

The for/else here saves me having to detect the [0, 0, 0, ..., 0] case specially.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.