You can solve this easily using a bit of math:

y=int(raw_input()) z=y while(z%3!=0): z-=5 if(z<0): print '-1' else:
print z*'5'+(y-z)*'3'

If the number(say 66317) is not divisible by 3, it will leave a modulo of either 0,1 or 2. If I decrease the number by 5, I am basically making it a multiple of 3, and the remaning digits will be a multiple of 5 as I am subtracting it from the number.

modulo 0 implies number divisibile modulo 1 implies 5 needs to be subtracted twice. modulo 2 implies 5 needs to be subtracted once.

Correct me if I am wrong. Completed all the test cases in 0-0.01s

Pro Tip for Java user: Use the StringBuilder class.

String is immutable, so everytime you add to a string, it creates a new object! With an input of 100000, you'd have created 30000 new objects each containing the string it was before it plus what you added to it! You can imagine how innefficient this is.

StringBuilder, 1 object, 1 problem solved. Use StringBuilder today!

(This message is brought to you by StringBuilder Co. We build Strings in a timely manner for you, so you don't have to!)

Gosh!! wasted 5 hours and only able to pass through 4 test cases.This should be marked as Hard :(

This post is not meant to provide a code answer (there are plenty of other posts that do that) but to explain how beginners should intellectually approach this problem and others like it.

By examining the specifications and eliminating the irrelevant ones, you can figure out how to solve the problem. You also reduce the potential of confusing yourself, becoming sidetracked onto solving something else, or overcomplicating the problem and your solution. 

Specifications:
1. The number must be of length N.
2. The number must contain only '3's and '5's.
3. The amount of '3's is divisible by 5.
4. The amount of '5's is divisible by 3.
5. If there are multiple acceptable matches, choose the largest one.

A. Due to #5, we recognize immediately that all '5's must come before all '3's. Therefore we can discard numbers like 53353533, for example.

B. Due to A, #3, and #4, we recognize that '3's will always come in a sequence of '33333' and '5's will always come in a sequence of '555'.

C. Due to #3 and #4, #2 is of little functional relevance. '555' is equivalent to 'XXX' and '33333' is equivalent to 'YYYYY' here, as long as all 'X's come before all 'Y's.

D. Due to A, B, C, #1, and #5, we recognize that we can use a greedy algorithm to solve this problem. Due to B, we know that 'XXX' takes absolute priority over 'YYYYY'. 'YYYYY' is only needed to "fill in" any remaining gaps. You can immediately find the closest match using 'XXX' only, then iterate downwards (remove X and add Y) until you find a valid string of exactly N length.

From the above, you can easily derive the necessary code in any language. This type of approach is broadly applicable to many other problems, not just this one. Knowledge of algorithm design techniques will be helpful.

My solution in python 3:

def decentNumber(n):
    if n % 3 == 0:
        print('5' * n)    
    elif n % 3 == 1 and n >= 10:
        print( '5'* (n - 10) + '3' * (10))
    elif n % 3 == 2 and n >= 5: 
        print('5' *(n - 5) + '3' * (5))
    else:
        print(-1)    
    return

When you divide by 3, you get remainder 0 or 1 or 2. If it 0, we can have a stirng of all 5's. If the remainder is 1, then if you subtract 10 ( which is 3 * 3 + 1) then the number is divisible by 3 -- however, number should be atleast 10. If remainer is 2, then if you subtract 5 (which is 3 *1 + 2) then the number is divisible by 3 -- however number should be at least 5. Otherwise, print -1.