Python sum pairs from text file

Question

I am given a sorted array of positive integers and a number X and I need to print out all pairs of numbers whose sum is equal to X. Print out only unique pairs and the pairs should be in ascending order.

However the program needs to read lines of text from standard input where each line contains a comma separated list of sorted numbers, followed by a semicolon, followed by the integer X.

e.g. test input:1,2,3,4,6;5 output: 1,4;2,3

I have tried

list1 = []
for line in sys.stdin:
    for n in line:
        list1.append(n)
        strlist = [ x for x in list1 if x.isdigit() ]
        numlist = list(map(int, strlist))
    sum = numlist[-1]
    res = []
    while numlist:
        num = numlist.pop()
        diff = sum - num
        if diff in numlist:
            res.append((diff, num))     
    res.reverse()
    print(res, end="")

But i get

Test Input: 1,2,3,4,6;5

Expected Output: 1,4;2,3

My Output: [(2, 3), (1, 4)]

Answer 1

Solution 1:

Time complexity of O(n^2). This is based on the original solution. The corrections made were:

• The iteration of the string and parsing per character wouldn't work for 2-digit numbers (or more) e.g. 12 thus it is incorrect. Also it is not efficient. Instead of manually iterating each character, checking .isdigit(), and then redoing it again for the next number for the whole list, just split the string by the characters ; and , and then transform them to int.
• In your original logic, the target sum would be the last element in the list numlist. But you are considering that number for the sum (since it will be the first number to be popped out). You should pop it first before entering the while loop.
• The order of the pairs would start from the highest number (pop until list is empty). So, the pair for the highest number would be the smallest number e.g. 1 is to 4, then 2 is to 3, thus no need to call .reverse() as it will do the opposite.

for input_text in [
    "1,2,3,4,6;5",
    "5,10,15,20,25,30,35,40,45;50",
    "0,2,4,6,8,10,12,14;12",
]:
    num_str, sum_str = input_text.split(';')
    num_list = list(map(int, num_str.split(',')))
    target_sum = int(sum_str)

    res = []
    while num_list:
        num = num_list.pop()
        diff = target_sum - num
        if diff in num_list:
            res.append((diff, num))     
    res_formatted = ";".join(map(lambda pair: f"{pair[0]},{pair[1]}", res))
    print(f"{input_text}\n\t{res}\n\t{res_formatted}")

Solution 2:

Time complexity of O(n). Since we already have sorted data, instead of iterating the whole list finding the other number that will arrive to the target sum for each number, just use 2 pointers, one at the start/left lhs and one at the end/right rhs.

• If the sum is lower than the target, then it means that we need to move forward/right the lhs. Why? Because if we already added it to the maximum number which is rhs, then there is no point of trying it with the other numbers. What we need is to increase lhs and see the next result.
• If the sum is higher than the target, then it means we need to move back/left the rhs. Why? Same point as above, If the sum was already higher, then we can't use the number in rhs as it is too high even if added with the smallest number lhs, thus move it to the next smaller number.
• If the sum is equal to the target sum, then we include in the result the numbers pointed to by lhs and rhs. Then we move both pointers respectively.

def sum_pairs(numbers, target_sum):
    lhs = 0
    rhs = len(numbers) - 1
    pairs = []
    while lhs < rhs:
        current_sum = numbers[lhs] + numbers[rhs]
        if current_sum == target_sum:
            pairs.append((numbers[lhs], numbers[rhs]))
            lhs += 1
            rhs -= 1
        elif current_sum > target_sum:
            rhs -= 1
        else:
            lhs += 1

    return pairs

for input_text in [
    "1,2,3,4,6;5",
    "5,10,15,20,25,30,35,40,45;50",
    "0,2,4,6,8,10,12,14;12",
]:
    num_str, sum_str = input_text.split(';')
    num_list = list(map(int, num_str.split(',')))
    target_sum = int(sum_str)

    res = sum_pairs(num_list, target_sum)

    res_formatted = ";".join(map(lambda pair: f"{pair[0]},{pair[1]}", res))
    print(f"{input_text}\n\t{res}\n\t{res_formatted}")

Output

1,2,3,4,6;5
    [(1, 4), (2, 3)]
    1,4;2,3
5,10,15,20,25,30,35,40,45;50
    [(5, 45), (10, 40), (15, 35), (20, 30)]
    5,45;10,40;15,35;20,30
0,2,4,6,8,10,12,14;12
    [(0, 12), (2, 10), (4, 8)]
    0,12;2,10;4,8

Answer 2

This might not be the most efficient, but I came up with this that worked.

Replace the test_case with sys.stdin and remove the test_case should work.

Sorry if this looks bad, it's my first time posting on stackoverflow.

test_case = ["1,2,3,4,6;5"]
for line in test_case:
    line = line.split(";")
    numbers = line[0].split(",")
    pairs = []
    for number in numbers:
        difference = int(line[1]) - int(number)
        difference = str(difference)
        if  difference in numbers and difference != number:
            pair = ",".join((number, difference))
            pairs.append(pair)
del pairs[len(pairs)//2:len(pairs)]
print(";".join(pairs))

Output : 1,4;2,3