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
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 > 33333
 8 > 5*(16%3) = 5 > 55533333
 10 > 5*(20%3) = 10 > 3333333333
 15 > 5*(30%3) = 0 > 555555555555555
Solution:
1
2
3
4
5
6
7
8
9
10
11
12

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) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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) 