Hello,
Today’s post is about solving a new interesting problem using python. We’ll be using Python 3 in this series of challenges.
Problem Statement:
Given a list of numbers and a number k
, return whether any two numbers from the list add up to k.
Bonus: Can you do this in one pass?
Example 1:
Input: List [10, 15, 3, 7], k =17
Output: True
Example 2:
Input: List [1,3,4,5,67,7], k= 73
Output: False or empty list or no output
SOLUTION:
First Approach:
Defining a function with 2 for loops. This is usually the conventional way of iterating through a list to find an elements that return sum equal to a given number.
def check_if_k_exists(input_list,k): for i in range(len(input_list)-1): for j in range(i+1,len(input_list)-1): if (input_list[i]+input_list[j+1])==k: return True k=17 input_list=[10, 15, 3, 7] print(check_if_k_exists(input_list,k))
Output:
EXPLANATION:
- Define value of k and input list. k=17, input_list=[10, 15, 3, 7]
- Define a function which iterates through the list and adds numbers to check if their sum is equal to k.
- First for loop iterates from 0 to (length of list -1).
- Second for loop iterates from 1 to (length of list -1).
- ITERATIONS for j loop:
- Iteration 1: i=0, j=1. check if input_list[i]+input_list[j+1]) is equal to k. input_list[0] is 10 and input_list[1] is 15. addition gives 25 which is not equal to 17.
- Iteration 2: i=0, j=2. check if input_list[i]+input_list[j+1]) is equal to k. input_list[0] is 10 and input_list[2] is 3. addition gives 13 which is not equal to 17.
- Iteration 2: i=0, j=3. check if input_list[i]+input_list[j+1]) is equal to k. input_list[0] is 10 and input_list[3] is 7. addition gives 17 which is equal to 17. It returns True
- Call the function with the input parameters and print the value returned by the function.
The above approach can also be done using List Comprehension.
result=[True for i in range(len(input_list)-1) for j in range(i+1,len(input_list)-1) if ((input_list[i]+input_list[j+1])==k)] print(result)
It uses the same logic as the above function, but the list comprehension is more compact.
Second Approach:
This approach is for the bonus defined above, to iterate the list in only one pass and return if the sum of 2 numbers is equal to k or not.
def check_if_k_exists(input_list,j): sorted_list=sorted(input_list) j=len(sorted_list)-1 for i in range(len(sorted_list)-1): if sorted_list[i]+sorted_list[j]<k: pass elif sorted_list[i]+sorted_list[j]>k: j-=1 else: return True k=22 input_list=[10, 15, 3, 7] print(check_if_k_exists(input_list,k))
Output:
EXPLANATION:
- Define value of k and input list. k=17, input_list=[10, 15, 3, 7]
- Define a function which sorts the list and stores it in the variable sorted_list. sorted_list has the values [3,7,10,15]
- Variable j stores the last index of the list. In this case it is index 3. sorted_list[3]=15
- Loop over the list starting from 0 to (length of sorted_list -1) which is 3 in this case.
- Iteration 1: i=0, j=3. checks if sorted_list[i] + sorted_list[j] is less than k. sorted_list[0]+sorted_list[3] returns 18 which is greater than k. Function skips to elif part.
- elif checks if sorted_list[i]+sorted_list[j] is greater than k which is true. It decrements j by 1,so the value of j becomes 2
- Iteration 2: i=1, j=2. checks if sorted_list[i] + sorted_list[j] is less than k. sorted_list[1]+sorted_list[2] returns 17 which is not less than k. Function moves to elif
- elif checks if sorted_list[i]+sorted_list[j] is greater than k which is not true in this case. Function moves to else part.
- else returns True.
- Iteration 1: i=0, j=3. checks if sorted_list[i] + sorted_list[j] is less than k. sorted_list[0]+sorted_list[3] returns 18 which is greater than k. Function skips to elif part.