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 = 4
then, 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