Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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?

share|improve this question
    
Can't you just people answer it rather than editing? :P nevamind. –  Mohammad Areeb Siddiqui Mar 7 at 15:04
    
How long did it take you to write the above code? –  rolfl Mar 7 at 15:15
    
10 min @rolfl :) –  Mohammad Areeb Siddiqui Mar 7 at 15:51
    
FYI, the Java solution below ranked with score 30... apparently the maximum. –  rolfl Mar 7 at 16:34

2 Answers 2

up vote 4 down vote accepted

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)
share|improve this answer

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 ) );
share|improve this answer
    
I didn't understand. –  Mohammad Areeb Siddiqui Mar 7 at 15:51
    
This fails in some cases if you pass in a string to getDecentNumber(). Try it with '3' rather than 3. Obviously the fix is to use n = parseInt(n) before the first var in getDecentNumber. The reason I mention this is using the code as-is in the hackerrank javascript boilerplate may lead to the issue. –  Greg Mar 7 at 17:11
    
Agreed, solved, but more subtly ;) –  konijn Mar 7 at 17:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.