import math
n=7 #length of list
k=2 #number
arr=[1,1,1,1,4,5,1]
l=n
def segmentedtree(segmentedtreearr,arr,low,high,pos): #function to build segment tree
if low==high:
segmentedtreearr[pos]=arr[high]
return
mid=(low+high)//2
segmentedtree(segmentedtreearr,arr,low,mid,((2*pos)+1))
segmentedtree(segmentedtreearr,arr,mid+1,high,((2*pos)+2))
segmentedtreearr[pos]=segmentedtreearr[((2*pos)+1)]+segmentedtreearr[((2*pos)+2)]
flag=int(math.ceil(math.log2(n))) #calculating height of segment tree
size=2*int(math.pow(2,flag))-1#calculating size
segmentedtreearr=[0]*(size)
low=0
high=l-1
pos=0
segmentedtree(segmentedtreearr,arr,low,high,pos)
if (n%2==0):
print (segmentedtreearr.count(k)+1)
else:
print (segmentedtreearr.count(k))
Now arr=[1,1,1,1,4,5,1]
so different possible combinations for sum equal to k=2
can be [1,1]
using index (0,1)
and [1,1]
using index (1,2)
and [1,1]
using index (2,3)
but i am getting 2 as a output although my implementation is correct.
Segment trees are good for looking up ranges when you have an absolute point, but in your case you have a relative measure you are looking for (a sum).
Your code is missing a pair of ones that are in two different branches of the tree:
As you can imagine, larger sums could span several branches (like for sum = 7). There is no trivial way to make use of this tree to answer the question.
It is much easier with a simple iteration through the list, using two indexes (left and right of a range), incrementing the left index when the sum is too large and incrementing the right index when it is too small. This assumes that all values in the input list are positive, which is stated in your reference to hackerrank:
def count_segments_with_sum(lst, total):
i = 0
count = 0
for j, v in enumerate(lst):
total -= v
while total < 0:
total += lst[i]
i += 1
count += not total
return count
print(count_segments_with_sum([1,1,1,1,4,5,1], 2)) # -> 3
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments