I have this following code which find every possible pair of numbers that sum up to n number
lst = [int(input()) for i in range(int(input()))] num = int(input()) #Amount to be matched cnt = 0 lst = list(filter(lambda i: i <= num, lst)) #Remove number that more than `num` for i in lst: for j in lst: if i+j == num: cnt += 1 print(int(cnt/2))
For example, if I enter
5 #How many numbers 1 < #Start of number input 4 < 5 7 1 < #End of number input 5 #Amount to be matched
It will return 2 because there is two pair that their sum is equal to 5 (1,4) and (4,1) (The number I marked with < ).
The problem is the complexity is O(n2) which will run slow on large input. I wanted to know if that is there a way to make this run faster?
10 #How many numbers 46 #Start of number input 35 27 45 16 0 < 30 < 30 < 45 37 #End of number input 30 #Amount to be matched
The pair will be (0, 30) and (0, 30) which will return 2.