Day #1: My Start With 100 Days Of Code

Hi! I'm Manish. I was wondering what to do in this COVID-19 pandemic, to stay a bit productive and then the phrase 100 Days Of Code striked me while surfing the internet and I decided to take up the challenge.

To begin with that, I have enolled for the email subscription by Daily Coding Problems. The team at DCP sends us an email with one coding problem a day and I believed that it would be the right thing for the challenge. To add to that, I have decided to share my experience on solving the question too and start writing on dev.

The Question On Day #1:

Given a list of numbers and a number `k`, return whether any two numbers from the list add up to `k`.

For example, given `[10, 15, 3, 7]` and `k` of `17`, return true since `10 + 7` is `17`.

My First Approach

• Input the given numbers into a list and and the sum to check in a variable.
• Traverse through the list and for each element at index i, check if there exists a complementary number starting from the index i in the list.
• If there exists atleast one such number print "pair exists" and exit the loop by marking a flag.
• After the cursor exits the loop adn if the flag is still unmarked, print "pair doesn't exist".

Python Code

l=[10,15,3,7]
k=17
flag=0
for i in range(len(l)-1):
    if (k-l[i]) in l[i+1:]:
        #slicing to prevent additional checks
        print("pair exists")
        flag=1
        break
if flag==0:
    print("pair doesn't exist")

Points To Note:

• The check for the complementary number is only done for the sliced list from i+1 to len(l), since the previous number pairs are already checked in the iterations before.
• The last element of the list is thus skipped from being checked for a complementary number.

Time Complexity Of The Above Solution

The traversal through the list takes a time of O(n) where n is the length of list. For each element, there is an another check with in operator which again takes a time complexity of O(n-i) for a list in python ref.

The total time complexity for the solution will result in a time complexity of O(n^2).

Better Approach

An approach better to the above solution is to convert the list into a set first, does making the in operator efficient to use.

The time complexity of using the in operator on a set is O(1) on average and O(n) in the worst case.

Python Code

l=[10,15,3,7]
k=17
s=set(l) #converting list l into a set and storing it in s
flag=0
for i in s:
    if (k-i) in s:
        print("pair exists")
        flag=1
        break
if flag==0:
    print("pair doesn't exist")

Time Complexity Of The Above Solution

The conversion from list to a set takes a time of O(n) where n is the length of list. Hence, the total time complexity for the above solution is O(n)+O(nx1)
[O(nx1) on average and O(nxn) in the worst case for the loop and condition check using in operator on the set s].

Thus the total time complexity on average results to O(n) and O(n^2) in the worst case scenario.

This question helped me in understanding the time complexities of individual data structure operations in python. I would love to hear from my fellow developers and take suggestions on improving the above logic. I am a pretty newbie to solving such questions, please consider it. I also request you to drop suggestions to improve my article readability or understanding.

Thanks and cheers:)