##### 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 Beast*with 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

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