Find the shortest subarray in an array, whose sum of indexes in the given array equals the sum of the elements of the subarray

Question

I'm almost a beginner programmer that wants to learn how to write algorithms.I just wrote a program that finds the shortest subarray(subset) in an array, whose sum of indexes in the given array equals the sum of the elements of the subarray(subset) and prints out the sum. The problem is, I needed to keep track of both the amount of numbers in the subarray(to find the shortest one) as well as the sum of the chosen elements(because I want to save it or just print it), so I would like to return a 2-element array recursively, but any way I try it, I end up having an error like "NoneType is not subscriptable" or '<' not supported between instances of 'NoneType' and 'NoneType'. So I used a global variable and solved it that way. But how do I avoid using a global variable in this type of problem? Here is my code, please teach me how to solve this type of problem without a global variable:

best_sum = math.inf

def SumIndexesEqualSumElements(T, idx=0, idxsum=0, tabsum=0, count=0):
    global best_sum
    if idx==len(T):
        if count==0:
            return math.inf
        if idxsum==tabsum:
            best_sum = tabsum
            return count
        return math.inf
    return min(SumIndexesEqualSumElements(T,idx+1,idxsum+idx,tabsum+T[idx],count+1),
               SumIndexesEqualSumElements(T,idx+1,idxsum,tabsum,count))

SumIndexesEqualSumElements([1,7,3,5,11,2])
print(best_sum)

Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. — Community
– Community Bot, Commented Dec 11, 2022 at 19:39

shubhranka varma · Accepted Answer · 2022-12-11 16:37:55Z

0

Your code is finding subset of the array having equal indices sum.

I suggest you to solve beginner level - subarray and subset question. Than, come to this.

For this question, you can brute force array, finding all the subarray sums and indices sum. Then, selecting the best one - shortest(here)

def SumIndexesEqualSumElements(arr):
    best_length = len(arr)
    ans_sum = 0
    for i in range(len(arr)):
        indices_sum = 0
        elements_sum = 0
        length = 0
        for j in range(i,len(arr)):
            indices_sum += j
            elements_sum += arr[j]
            length += 1
            if indices_sum == elements_sum:
                if length < best_length:
                    best_length = length
                    ans_sum = elements_sum
    return ans_sum
print(SumIndexesEqualSumElements([1,3,3,0,11,2]))

using 0 - based Indexing

answered Dec 11, 2022 at 16:37

shubhranka varma

535 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Stiffo Over a year ago

I meant to consider all subsets of the array, not necessarily consecutive elements. Thank you for your effort though.

Collectives™ on Stack Overflow

Find the shortest subarray in an array, whose sum of indexes in the given array equals the sum of the elements of the subarray

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related