python - Efficient & Pythonic way of finding all possible sublists of a list in given range and the minimum product after multipying all elements in them? -
i've achived these 2 things.
find possible sublists of list in given range
(i ,j).
a = [ 44, 55, 66, 77, 88, 99, 11, 22, 33 ] let, = 2 , j = 4then, possible sublists of list
"a"in given range(2,4):[66], [66,77], [66,77,88], [77], [77,88], [88]and, minimum of resultant product after multipying elements of sublists:
so, resultant list after multiplying elements in above sublists becomex = [66, 5082, 447216, 77, 6776, 88]`now, minimum of above list,
min(x)i.e66
my code:
i, j = 2, 4 = [ 44, 55, 66, 77, 88, 99, 11, 22, 33 ] o, p = i, mini = a[o] while o <= j , 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 taking more time executed larger lists , larger ranges !
there possible "pythonic" way of reducing time complexity of above code ?
in advance !
edit :
got it. but, if there more 1 such possible sublist same minimum product,
- i need longest sub list range
(i,j) - if there still more 1 sublists same "longest sub range", need print sub-interval has lowest start index.
consider list a = [2, 22, 10, 12, 2] if (i,j) = (0,4).
there tie. min product = 2 2 possibilities '(0,0)' , '(4,4)' .
both sub list range = 0 [ (0-0) , (4-4) ]
in case need print (minproduct, [sublist-range]) = 2, [0,0]
tried using dictionaries, works inputs not ! how 'efficiently' ?
thank !
first, given list , index range, can sublist a[i : j + 1]
[66, 77, 88] for positive integers a , b, a * b no less a or b. don't need multiplying, it's not possible multiplying of 2 or more elements has smaller result. minimum of list is minimum of multiplying results.
so result is:
min(a[i : j + 1])
Comments
Post a Comment