Subramanian ðŸ˜Ž

Posted on

# Python Programming Challenge

I came across this problem in an online hiring challenge.

# The Challenge

Find a position X in the array A consisting of N elements, such that the difference between A[0] x A[1] x ... x A[X] and A[X+1] x A[X+2] x ... x A[N-1] is minimum.

How would you approach this problem in time as well as space efficient way?

# My Approach #1

I had two arrays leftArr and rightArr that store the left and right subarray product for each element in the array A.

Then I created another array difference to hold the absolute difference between corresponding elements in leftArr and rightArr.

I used index() and min() function to find the index of the smallest element in the difference array.

RESULT: Memory Limit Exceeded! (for almost all test cases except 2)

# My Approach #2

I found the two product arrays to be redundant.

This time, instead of storing the product in arrays, I used two variables leftProduct and rightProduct.

I got rid of the difference array too and instead, had new minDiff and minDiffIndex variables to find the minimum difference and it's index.

Initially, I calculated the product of the entire array and stored it in the rightProduct.

Then, I iterated over the array once again and at each stop, I multiplied the current number with the leftProduct and divided the rightProduct.

Simultaneously, I calculated the difference and saved the index if the difference was found to be smaller than the minDiff.

Finally, I printed the minDiffIndex.

RESULT: Time Limit Exceeded! (for the same test cases)

# Conclusion

After being unsuccessful, I gave up and came over to dev.to to ask for better approaches and suggestions.

If you have a better approach in mind, do comment below!

Cheers!

Mat • Edited

By time limit exceeded I assume you mean they wanted to the running time of the algorithm to be faster? If so I think you have a good starting point in your second solution.

I don't have the answer, but I would probably think about why that algorithm is so slow, which might depend on the size of the numbers being multiplied or the size of the arrays themselves.

If the numbers are large maybe there is a way to know something about the difference of the two products without computing the actual products.
For example, without calculating anything I know that the product of [13,27] is less than [14,28], and both will be closer to each other than [13,28,92].

The other thing that comes to mind is you basically have have (N-2) possible values of X, but maybe you don't need to examine all of them? For these kinds of problems I find it helpful to work through the algorithm manually and see where I could cut corners.

My thought process goes something like this:

• If you start with N=1 then you have only 1 number in the left array, and all the other numbers in the right array.
• This makes me wonder if N=1 is always the worst case, but there is a counterexample: the number on the left hand side could be 9 and all the other numbers could be very low, like [3,1,1,1,1,3].
• Maybe the array could contain zeros as well
• If there are multiple zeros you can choose any X between 2 of the zeros and then the difference will be zero
• If there is a single zero, one of the products will be zero and the other will be non zero. Then you can choose X to make the non zero part is as small as possible
• assuming the numbers are integers then the smallest non zero part will be a single number: either X=1 or X=N-2
• So in special cases you can avoid multiplication entirely
• What about a non-special case: [3,2,7,1,5]?
• Let's say we do start with N=1: I've multiplied all the numbers together and I divide by 3. Did I need to know the full product for that?
• I've done 3x2x7x1x5/3 so I needed most of it but the two 3s cancelled out, so I didn't need the full product
• And for N=2 I've done 3x2x7x1x5/3/2. This doesn't seem like the easiest way to calculate that
• If I have N>1 then I have `minDiff` target I need to beat - in this case I case I don't need to know the exact diff, if I can prove it's bigger than `minDiff`
• Given two arrays [A_1,A_2...A_X], [A_X+1 ... A_N] can I break the calculation into parts and do that check part way through?
• If I calculate the product of one array as Z then the product of the second array must be less than `minDiff+Z` to be worth calculating
• If the numbers are integers, and we've already ruled out zeros, then calculating the product step by step will cause the number to get bigger each iteration
• So we can stop early if we exceed `minDiff`
• Also, if we get to this point and the second array is smaller than the first, then increasing X won't help, so we can terminate early and return `minDiff`

I doubt this thought process would get me anywhere in an interview setting, but I think it would give me some ideas for different approaches. Even if these ideas don't work, I think I'd learn something about the problem from exploring them.

Subramanian ðŸ˜Ž

That's some good insight into the problem!

Also now I'm wondering whether my choice of programming language was the reason for timeout.

Usually in most online platforms, the timeout would be different for different programming languages right?

But the time and memory constraints for this problem was fixed at something like 2s and 350 MB. (I'm unable to check now. The challenge has ended)

And the input was quite large. When I used the / operator, I got an error saying can't divide such a huge float or something like that. I had to use // instead to do integer division.

So maybe, I should have tried in C++/Go too.

Idan Arye

The trick is that you can deduce the products for the next `X` from the ones of the current `X` without multiplying everything again:

``````prod(A[0]..A[X+1]) = prod(A[0]..A[X]) * A[X+1]
prod(A[X+2]..A[N-1]) = prod(A[X+1]..A[N-1]) / A[X+1]
``````

Using that, you just need two passes on the array - once to get the initial product of the second half (the entire array) and once again to update the products for each element and find the minimal difference:

``````def splitted_sums(array):
from functools import reduce
from operator import mul
first_half_sum = 1
second_half_sum = reduce(mul, array, 1)
for i, elem in enumerate(array):
first_half_sum *= elem
second_half_sum /= elem
yield i, first_half_sum, second_half_sum

index = min(splitted_sums(array), key=lambda t: abs(t[1] - t[2]))[0]
print(index)
``````

Subramanian ðŸ˜Ž

How is this different from my second approach?

Idan Arye

Now that I look at it - it isn't. I was probably not paying enough attention when I looked at your original post, and thought that you are calculating the entire products for each index...

The time complexity should be linear, and because every element can change the result you can't have sublinear complexity. So how did you exceed the time complexity? Are they timing the actual run instead of doing complexity analysis?