Python Daily Challenge

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:

1. Define value of k and  input list. k=17, input_list=[10, 15, 3, 7]
2. Define a function which iterates through the list and adds numbers to check if their sum is equal to k.
   1. First for loop iterates from 0 to (length of list -1).
   2. Second for loop iterates from 1 to (length of list -1).
   3. ITERATIONS for j loop:
      1. 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.
      2. 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.
      3. 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
3. 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:

1. Define value of k and  input list. k=17, input_list=[10, 15, 3, 7]
2. Define a function which sorts the list and stores it in the variable sorted_list. sorted_list has the values [3,7,10,15]
3. Variable j stores the last index of the list. In this case it is index 3. sorted_list[3]=15
4.  Loop over the list starting from 0 to (length of sorted_list -1) which is 3 in this case.
   1. 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.
      1. 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
   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
      1. 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.
      2. else returns True.