I have to find the largest 'decent number' having
N digits. A decent number has the following properties:
- 3, 5, or both as its digits. No other digit is allowed.
- Number of times 3 appears is divisible by 5.
- Number of times 5 appears is divisible by 3.
My code works perfect, but, I am afraid it is far from efficient:
4 #number of test cases, i.e., the following 4 inputs 1 3 5 11
-1 555 33333 55555533333
My version of the solution:
T = int(input()) #number of test cases def computePair(N): multiplesOf3 = [i for i in range(N+1) if i%3 == 0] if multiplesOf3 != : #reversing a  results in a 'NoneType' multiplesOf3.reverse() multiplesOf5 = [i for i in range(N+1) if i%5 == 0] for i in multiplesOf3: for j in multiplesOf5: if (i+j) == N: return (i, j) return -1 for testCase in range(T): N = int(input()) #test case result = computePair(N) if result == -1: print(result) #If no such combination exists return '-1' else: print('5' * (result) + '3' * (result))
I assume my code has a time-complexity of \$O(n^2)\$; because of the two
for loops. I want this to be more efficient in the order of \$O(n)\$ - linear.
This is a very generic question: also, do you have any resources to time-complexity best practices? I suck at it.