# 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.

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.

• 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.