Sherlock and The Beast

I have recently written the program for the Sherlock and The Beast' HackerRank challenge. That's working fine, but the problem is that it takes too much time if a big number is given as a input. I would like you to help me out in optimizing my code so that it could run under 16 seconds, which is needed.

from collections import Counter
def isDecent(n):
    digits = list(map(int, str(n)))
    if not set(str(n)).issubset('35'): return False
    threes = Counter(digits)[3]
    fives = Counter(digits)[5]
    if threes % 5 == 0 and fives % 3 == 0: return True
    else: return False

inps = []
decents = []
t = int(input())
for i in range(t): inps.append(int(input()))
for inp in inps:
    if inp == 1:
        decents.append(-1)
        continue
    n=2
    while True:
        if(isDecent(n) and len(str(n)) == inp): break
        n+=1
    if n != 2: decents.append(n)
    else: decents.append(-1)
for decent in decents: print(decent)

Is there any thing that could be used to optimize it?

Your algorithm is way off.... ;-)

Let's consider the solution to a decent number.

For any decent number, the more 5's we put at the front, the better.

So, let's break it down to some maths....:

• d => number of digits in the decent number

• f => number of fives in the decent number

• t => number of threes in the decent number

also

• d = f + t

• f % 3 == 0

• t % 5 == 0

We have:

d = f + t

Algorithm:

// tmp number of five values is the number of digits
ftmp = d
// decrease the number of fives (by the number of threes in a batch)
// until both the rules f % 3 == 0 and t % 5 == 0 are satisfied
while ftmp % 3 != 0 : ftmp -= 5

check the ftmp is a valid value
if ftmp % 3 != 0 : return -1;

f = ftmp;
t = d - f

return "5" x f + "3" x t

Writing it in Java, I have the following:

private static String sherlock(final int target) {
int threes = 0;
int fives = 0;
int digits = target;
while (digits > 0) {
if (digits % 3 == 0) {
fives = digits;
break;
}
digits -= 5;
}
threes = target - digits;
if (digits 0) {
sb.append("5");
}
while (threes-- > 0) {
sb.append("3");
}
return sb.toString();
}


For me, on my laptop, this solves the 100000 digit problem in less than 1 millisecond. First I 'warm up' Java with the first 10,000 solutions....

Then I run some big ones....

public static void main(String[] args) {
int cnt = 0;
long ms = System.currentTimeMillis();
for (int i = 0; i 20 ? "too long" : val, nanos / 1000000.0);
}
}


This produces the output:

Warmup created 49995011 characters in 703 Milliseconds
request digits 1 : actual digits 5 Value 33333 in (0.004ms)
request digits 3 : actual digits 3 Value 555 in (0.012ms)
request digits 5 : actual digits 5 Value 33333 in (0.003ms)
request digits 11 : actual digits 11 Value 55555533333 in (0.002ms)
request digits 19 : actual digits 19 Value 5555555553333333333 in (0.002ms)
request digits 100000 : actual digits 100000 Value too long in (0.622ms)

StackExchange Code Review Q#43709, answer score: 8