Sherlock and The Beast
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 &gt; 0) {
        if (digits % 3 == 0) {
            fives = digits;
            break;
        }
        digits -= 5;
    }
    threes = target - digits;
    if (digits &lt; 0 || threes % 5 != 0) {
        return "-1";
    }
    StringBuilder sb = new StringBuilder(target);
    while (fives-- &gt; 0) {
        sb.append("5");
    }
    while (threes-- &gt; 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 &lt; 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() &gt; 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)