Sherlock and The Beast

Question

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?

Answer 1

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 || threes % 5 != 0) {
        return "-1";
    }
    StringBuilder sb = new StringBuilder(target);
    while (fives-- > 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 < 10000; i++) {
        cnt += sherlock(i).length();
    }
    ms = System.currentTimeMillis() - ms;
    System.out.println("Warmup created " + cnt + " characters in " + ms + " Milliseconds");
    for (int i : new int[] { 1, 3, 5, 11, 19, 100000 }) {
        long nanos = System.nanoTime();
        String val = sherlock(i);
        nanos = System.nanoTime() - nanos;
        System.out.printf("    request digits %d : actual digits %d Value %s in (%.3fms)%n",
                i, val.length(), val.length() > 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)

Answer 2

Your approach seems all wrong, throw all that code away <- that's the code review.

You have to think about combinations, this is not like finding prime numbers.

n:1 -> Because you can only build numbers with 33333 and 555 you cannot find anything

n:2 -> same as 1

n:3 -> Can only be '555', again because your building blocks for the number are 555 and 33333

n:4 -> Impossible, you cant use 33333 ( too long ) and if you used 555 then you have 1 digit left which is useless

n:5 -> Can only be 33333, that's the only thing that fits

etc. etc.

You have to fit in blocks of 5 and 3 digit strings to get to n'.

The last tip as per the question, for n=8 you could have

55533333 or 33333555, obviously you need to try to put 555 in front because 5 > 3.

Hope this helps.

Edit: The code of @rolfl should do the trick otherwise you can perhaps find inspiration in the JS version ( http://jsbin.com/dalor/2/edit ):

function repeatString( s , n )
{
  return n ? new Array( n + 1 ).join( s ) : "";
}

function getDecentNumber( n )
{
    var threes = 0,
        fives  = 0,
        remainingDigits = +n;
    while (remainingDigits > 2) {
        if (remainingDigits % 3 === 0) {
            fives = remainingDigits;
            break;
        }
        remainingDigits -= 5;
    }
    threes = n - fives;
    if (remainingDigits < 0 || threes % 5)
        return "-1";

    return repeatString( '5', fives ) + repeatString( '3', threes );
}

console.log( getDecentNumber( 1 ) );
console.log( getDecentNumber( 3 ) );
console.log( getDecentNumber( 5 ) );
console.log( getDecentNumber( 8 ) );
console.log( getDecentNumber( 11 ) );