Python program to find sub-list that adds up to a key

user_14773854 0
Viewed 677

I was asked to write a python function that verifies if there is at least one consecutive sequence of positive integers within the list l (i.e. a contiguous sub-list) that can be summed up to the given target positive integer t (the key) and returns the lexicographically smallest list containing the smallest start and end indexes where this sequence can be found, or returns the array [-1, -1] in the case that there is no such sequence. For example a list l containing the elements [4, 3, 5, 7, 8] and the key t as 12, the function would return the list [0,2] since the list contains the indexes of the values 4,3 and 5 and another list l containing the elements [1,2,3,4] and key t to be 15, the function would return [-1,-1] because there is no sub-list of list l that can be summed up to the given target value t = 15. I am supposed to write a function that identifies the first given sub-list that sums up to the key t, it should hence only return one sub-list. The sub-list can only be identified by the following:

  • Each list l will contain at least 1 element but never more than 100.
  • Each element of l will be between 1 and 100.
  • t will be a positive integer, not exceeding 250.
  • The first element of the list l has index 0.
  • For the list returned by solution(l, t), the start index must be equal or smaller than the end index. So far I have been able to implement the first two examples I had mentioned earlier. This is what I have tried so far:
def solution(l, t):
    if len(l) <= 100 and len(l) > 0 and t > 0 and t <= 250:
        if all(a<100 for a in l):
            for j in range(0, len(l) - 1):
                for k in range(0, len(l)):
                    for m in range(0, len(l)):
                        if l[j] + l[k] == t or l[j] + l[k] + l[m] == t:
                            if j + 1 == k and k + 1 == m:
                                return (j, k) if l[j] + l[k] == t else (j,k, m) if l[j] + l[k] + l[m] == t else (-1,-1)
            return (-1,-1)
        else:
            return False
    else:
        return False

My function only returns a list of maximum 3 values and I want it to return any number of values. Please help me as this is due in 4 days. Help is very much appreciated and please go easy on me as I have little experience in python.

python
2 Answers
def find_seq(inp_list,target):
    start = end = 0
    while start < len(inp_list):
        value = sum(inp_list[start:end+1])
        if value > target:
            start += 1
            if start > end and end < len(inp_list):
                end += 1
        elif value < target:
            if end < len(inp_list):
                end += 1
            else:
                return [-1,-1]
        else:
            return [start,end]
    return [-1,-1]
find_seq([4, 3, 5, 7, 8],12) # [0, 2]

Since you are focusing on consecutive sublists of positive integers, you can simplify the problem.

We restrict ourselves to move left to right through the numbers i.e. the start/ends can only increment, never decrement. This should not cause us to lose any solutions because we can reach any possible sublist by starting at the beginning and incrementing the start/end of our selected sublist and for additional reasons explained further below.

Given a consecutive sublist, your value can be too big, too small, or equal to the target. If it is equal to the target, then you are done.

If it is too big, then you need to remove some numbers. Since we are only moving right, the only way to remove numbers is by incrementing the start. To ensure we don't skip over any solutions, we increment the start by the smallest amount possible, which is 1. We cannot let the start go beyond the end of our sublist, so if the start and end are equal to each other, we have to increment both. We cannot let the end go past the end of the input list, so we only increment the end when we are able to.

If the current sublist sum is too small on the other hand, we need to add numbers. This means we need to increment the end, which will give us one new number to include in the sum. Since the end cannot go past the end of the input list, we only increment if we are able to. If we are unable to, then that means we have no numbers to add and our value is too small. This means we will never reach the value and we can terminate with a (-1,-1) result (no matches adding to target).

You might ask, well why don't we move the start backwards? Well if we did, we would have a value that was too big (even excluding the final number in the input list), and that has to have been true for our end index to reach the end. Remember the start index is only incremented when a previous sum is too big, so at some point we incremented that start index because the sum was too big. Since that decision, we have moved the end forward adding even more things. So moving the start backwards would result in a sublist that was too big.

Finally, if start ever reaches the end of the input list, then we have gone through all possibilities and found nothing.

From a performance perspective, you can make it so you don't have to sum the whole start to end sublist every loop iteration by tracking just one sum value and adding the new value each time you increment the end and subtracting the old left value each time you increment the start. I didn't bother to do this, but you can.

user_149418190

This can solve the task:

def summing_up_target(lst, t):
    for i in range(len(lst)):
        for ii in range(i,len(lst)):
            if sum(lst[i:ii]) == t:
                return [i,ii]
            elif sum(lst[i:ii]) > t:
                break
    return [-1, -1]

summing_up_target([4, 3, 5, 7, 8], 12)

Explanation:

  • You iterate your input list by slicing into sublists.
  • If one of the sublists match the target, then return True, in case the sum of the sublist goes beyond the target, move to the next index in the list and keep slicing from there
user_17738410
Related