HackerRank: Maximum Draws

Second round of the fundamental mathematics problems on HackerRank is called Maximum draws.  It asks the following

Jim is off to a party and is searching for a matching pair of socks. His drawer is filled with socks, each pair of a different color. In its worst case scenario, how many socks (x) should Jim remove from his drawer until he finds a matching pair?

Input Format
The first line contains the number of test cases T.
Next T lines contains an integer N which indicates the total pairs of socks present in the drawer.

Output Format
Print the number of Draws (x) Jim makes in the worst case scenario.

To be honest this was an extremely easy solvable problem. In the worst case Jim can draw a number of socks equal to the amount of pairs and have exactly one sock from each pair. The next sock he draws will then always match one of the already drawn socks.

Or in other words the maximum draws is the number of pairs of socks +1.

In python this can be implemented by

def maximumDraws(n):
    return n + 1 

I have for the sake of brevity only included the function which is called to give the answer, instead of including all the input handling as well.

Posted by Kristian


Mitali Jain

But isn’t it like if there are 4 pairs of socks, then if we take out 4+1=5 socks, then 3 socks are still reamining in it. So how can we still pair the matching socks?

@Mitali. The question says “Jim is off to a party and is searching for a matching pair of socks.” emphasis on “a matching pair of socks”.

If there are 4 pairs of socks we have a total of 8 socks of 4 different colors. If someone removes one random sock say Red and in the second draw the sock is Blue and in the third draw if the sock is again Blue he’s got a matching pair!

Hence in the worst-case scenario, he would have to be drawing a different color every time so that is 4 (n) colors plus an extra sock which matches at the end!

Aviv Murlakov

@Mitali Jain
You need to match pairs from the socks you remove from the closet, not from the remaining in the closet.
If there are 4 socks a-a’, b-b’, c-c’, d-d’ then the worst case after 4 draws is that you have a (or a’), b (or b’), c (or c’), d (or d’). The 5th draw will have to match a pair with one of those.

Leave a Reply