I've achived these two things.
Find all possible sublists of a list in given range
(i ,j)
.
A = [ 44, 55, 66, 77, 88, 99, 11, 22, 33 ] Let, i = 2 and j = 4
Then, Possible sublists of the list
"A"
in the given range(2,4)
is :[66], [66,77], [66,77,88], [77], [77,88], [88]
And, minimum of the resultant product after multipying all the elements of the sublists:
So, the resultant list after multiplying all the elements in the above sublists will becomeX = [66, 5082, 447216, 77, 6776, 88]`
Now, the minimum of the above list, which is
min(X)
i.e66
My Code:
i, j = 2, 4
A = [ 44, 55, 66, 77, 88, 99, 11, 22, 33 ]
O, P = i, i
mini = A[O]
while O <= j and P <= j:
if O == P:
mini = min(mini, reduce(lambda x, y: x * y, [A[O]]))
else:
mini = min(mini, reduce(lambda x, y: x * y, A[O:P + 1]))
P += 1
if P > j:
O += 1
P = O
print(mini)
My Question:
This code is taking more time to get executed for the Larger Lists and Larger Ranges !
Is there any possible "Pythonic" way of reducing the time complexity of the above code ?
Thanks in advance !
EDIT :
Got it. But, If there is more than one such possible sublist with the same minimum product,
- I need the longest sub list range
(i,j)
- If there are still more than one sublists with the same "longest sub range", I need to print the sub-interval which has the lowest start index.
Consider this list A = [2, 22, 10, 12, 2]
if (i,j) = (0,4)
.
There is a tie. Min product = 2
with two possibilities '(0,0)' and '(4,4)'
.
Both sub list range = 0 [ (0-0) and (4-4) ]
In this case i need to print (minproduct, [sublist-range])
= 2, [0,0]
Tried using dictionaries, It works for some inputs but not for all ! How to do this 'efficiently' ?
Thank you !
First, given the list and the index range, we can get the sublist
A[i : j + 1]
For positive integers
a
andb
,a * b
is no less thana
orb
. So you don't need to do multiplying, it's not possible that multiplying of two or more elements has a smaller result. The minimum of this list is the minimum of all the multiplying results.So the result is: