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)