Number of distinct contiguous subarray

Om Sharma
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.

trincot

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:

enter image description here

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.

edited at
0

Comments

0 comments
Login to comment

Related

What is contiguous subarray

contiguous subarray within an array (containing at least one number) which has the largest sum

how to find the length of the longest contiguous subarray whose sum is divisible by a given number

Debugging: Largest Sum Contiguous Subarray

Algorithms question: Largest contiguous subarray selection

Largest sum contiguous subarray (Interview Question)

Print SubArray of Maximum Contiguous product in Array

largest sum of contiguous subarray No Larger than k

How to return the length of a contiguous subarray with specific criteria

Maximum sum of any contiguous subarray of the array

Elegant way to find contiguous subarray within an array in JavaScript?

Maximum sum in a contiguous subarray of a given 2D array

How can I find a subarray with some contiguous elements randomly in C?

Find maximum non contiguous subarray that respect a specific rule

How to check if sum of some contiguous subarray is equal to N?

Faster Numpy: Contiguous Number Replacement

Count the number of contiguous equal characters

Sort by contiguous digits as a single number

MongoDB: Distinct values from objects in subarray

Algorithm for the largest subarray of distinct values in linear time

Maximum subarray with given number of elements

Generate subarray with equal number elements

Counting number of contiguous column values in pandas df

Return contiguous 0's in a given binary number

Get the number of contiguous same numbers for an array

Random number generation in R without a contiguous repeat

Number of distinct islands

Number of distinct days in pandas

Distinct number of XORs