HackerRank ‘Sherlock and The Beast’ Solution

Short Problem Definition:

Sherlock Holmes suspects his archenemy, Professor Moriarty, is once again plotting something diabolical. Sherlock’s companion, Dr. Watson, suggests Moriarty may be responsible for MI6’s recent issues with their supercomputer, The Beast.

Shortly after resolving to investigate, Sherlock receives a note from Moriarty boasting about infecting The Beastwith a virus; however, he also gives him a clue—a number, . Sherlock determines the key to removing the virus is to find the largest Decent Number having digits.

Link

Sherlock and The Beast

Complexity:

time complexity is O(1)

space complexity is O(1)

Execution:

I am presenting two solutions. The naive brute force solution executes in O(N) and passes all the tests. Yet further optimisations and a runtime complexity of O(1) are possible.

When observing the possible output space we realise that there can only be 0, 5 or 10 threes in the output. If there would be 15 threes, it is better to use fives instead. The number of trailing threes can therefore be defined by K = 5*((2*N)%3). Let us plug some numbers into the equation:

  • 1 -> 5*(2%3) = 10 -> INVALID
  • 2 -> 5*(4%3) = 5 -> INVALID
  • 3 -> 5*(3%3) = 0 -> 555
  • 4 -> 5*(8%3) = 10 -> INVALID
  • 5 -> 5*(10%3) = 5 -> 33-33-3
  • 8 -> 5*(16%3) = 5 -> 555-33-33-3
  • 10 -> 5*(20%3) = 10 -> 33-33-33-33-33
  • 15 -> 5*(30%3) = 0 -> 555-555-555-555-555
Solution:
def sherlockBeast(N):
    K = 5*((2*N)%3)
    if K > N:
        return -1
    else:
        return '5' * (N-K) + '3'*K

if __name__ == '__main__':
    t = input()
    for _ in xrange(t):
        n = input()
        print sherlockBeast(n)
def sherlockBeastNaive(N):
    if (N < 3): return "-1" three_cnt = N//3 five_cnt = 0 while three_cnt >=0:
        rem = N - three_cnt*3
        if rem % 5 == 0:
            five_cnt = rem/5
            break
        three_cnt -= 1
        
    if three_cnt <= 0 and five_cnt == 0:
        return "-1"
    
    return "555"*three_cnt + "33333"*five_cnt

if __name__ == '__main__':
    t = input()
    for _ in xrange(t):
        n = input()
        print sherlockBeastNaive(n)

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin
  • Kevin Lobo

    Can you please explain as to how did you obtain the equation for K?

    • Hi Kevin,

      I am reasonably bad at explaining mathematical equations with proofs 🙂

      ((2xN)%3) is an inversion of N+N-K to the search space of 0,1,2. Times 5 is a simple requirement from the description.

  • Upon review I see that this question requires a longer explanation.

    Let us first examine the first solutions:

    01:-
    02:-
    03:555
    04:-
    05:33333
    06:555555
    07:-
    08:55533333
    09:555555555
    10:3333333333
    11:55555533333
    12:555555555555
    13:5553333333333
    14:55555555533333
    15:555555555555555

    We can notice that the number of threes is repeating in a pattern 2,1,0,2,1,0… This is a reverse function to N%3. We can reverse the operation by applying (N*(M-1))%M. Because M == 3, we can reverse it by doing (N*2)%3.

    Are there exceptions? Yes there are.

    ) N % 3 = 1 -> K = 2, N >= 10, INVALIDS 1,4,7
    ) N % 3 = 2 -> K = 1, N >= 5, INVALIDS 2
    ) N % 3 = 0 -> K = 0

    What is happening? Why are there exceptions? Well, we can imagine the operation also as follows:
    ) N % 3 = 1 means that three pairs of fives (9) need to be replaced by two pairs of threes (10). This is of course only possible if there is enough space for two pairs of threes. Therefore N >= 10
    ) N % 3 = 2 means that one pair of fives (3) needs to be replaced by one pair of threes (5). This is of course only possible if there is enough space for a pair of threes. Therefore N >= 5

    We can express this function with three ifs and a comaprison to 5/10. Or we can express it as one simple equation (because of the reversion of modulo).

    K = ((N*2)%3)*5

    Remember that we still need to handle the special cases. Let us observe the equation

    INVALIDS:
    1 -> ((2*1)%3) * 5 = 10
    4 -> ((2*4)%3) * 5 = 10
    7 -> ((2*7)%3) * 5 = 10
    2 -> ((2*2)%3) * 5 = 5

    Do you see how we return to the first explanation of the invalids? We can also notice that the result is bigger than the original N. Therefore if K > N return -1.

    Simple.