# Sherlock and The Beast

# Sherlock and The Beast

theroadtaken123 + 74 comments 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

snapdragon1 + 1 comment [deleted]vishalbty + 0 comments **Here's how I solved it using divmod.**

yeremy + 2 comments You're my hero. Thanks for the tip!!

theroadtaken123 + 1 comment Thank you yeremy, appreciate the reply :)

Amudala + 1 comment Thanks for posting it.

pardonmydust4 + 0 comments [deleted]

Mang_ + 2 comments It's a great solution. If I understand correctly, you separate N in two numbers: a multiple of 3 and a multiple of 5.

Is there a name to this mathematical procedure ?

rosiezou + 2 comments It is called a linear combination. In this case, it is a linear combination of 3 and 5.

edz65536 + 1 comment More specifically it is a Diophantine equation.

amdokamal + 0 comments There is an alternative solution, but not so efficient (but still O(1) in spite of recursion) and not so elegant as the Diophantine equation. This is linear congruence equation: 5x = n (mod 3). You can solve it by means of the extended Euclidean algorithm. I am aware that this is like 'A sledgehammer to crack a nut', but fyi. Here you can practise with the linear congruence.

theroadtaken123 + 0 comments Thank you mang, appreciate the reply :)

AntonDeCode + 16 comments 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!)

ifigu003 + 0 comments Thanks man. Now all the test cases are accepted.

yeremy + 1 comment Wow... didn't know how powerful StringBuilder is. Thank you!

pardonmydust4 + 0 comments ok you are the best

Hmpflabul + 0 comments MVP :')

asbear + 4 comments This function works quicker than of editorial.

`// return negative number if not found // otherwise pivot is returned. // caller can print 5 x pivot + 3 x (n-pivot) int getPivot(int n) { while(n > 0) { if(n%3 == 0) break; else n -= 5; } return n; }`

So you can do this:

`int pivot = getPivot(n); if(pivot < 0) cout << "-1" << endl; else { int repeat = pivot/3; while(repeat--) cout << "555"; repeat = (n-pivot)/5; while(repeat--) cout << "33333"; cout << endl; }`

edmondkwan + 3 comments am i missing somethign here? The editorial solution is O(1) how is this faster?

BSathvik + 0 comments you see O(1) means that its constant time but the constant(Eg:O(1000000)=O(1)) however big is rewritten as O(1) for the sake of simplicity. well maybe what he is trying to say is that maybe his constant is smaller(i am not sure if it is). i i am just trying to tell you that Alg1 maybe faster than Alg2 even though both of them hve the complexity of O(1).

SnoopDizzle + 0 comments The loop in this iterative approach will run at most 2 times, which technically makes this solution O(1) as well. However, it should be obvious that the direct formula will require fewer machine instructions. By counting just the math operations (so ignoring jumps, which inflate the cost even more), it breaks down like this (please comment if I made a mistake!):

`Direct (2 x N % 3): + 1 Multiply + 1 Mod = 2 Constantly`

Iterative:

`Best Case (N is divisible by 3): + 1 Comparison ( while(n > 0) ) + 2 Comparison and Mod ( if(n%3 == 0) ) = 3 Worse Case (N % 3 == 1), full loop runs twice: + 3 Comparison ( while(n>0) ) + 6(3x2) Comparison and Mod ( if(n%3 == 0) ) + 2(2x1) Subtraction ( n -= 5 ) = 11`

And we might as well do the 3rd case (loop runs once):

`+ 2 Comparison ( while(n>0) ) + 4(2x2) Comparison and Mod ( if(n%3 == 0) ) + 1 Subtraction ( n -= 5 ) = 7`

Since each case is equally likely, we calculate that the average cost is (3+7+11)/3 = 7 instructions.

So although both solutions are O(1), we can correctly conclude that the iterative approach is ~3 times more expensive. If we counted jumps and assignments, it's more like ~4 times. This is a significant difference.

big_endian + 1 comment It fails in some cases for ex: when N=1000 :P. PS: adding if(pivot%3!=0) pivot=getPivot(pivot); before checking for if(pivot<0) solves the prolem.

asbear + 1 comment I might be wrong :). But I can still get a result even with N=1000. What is the correct answer for N=1000? Also I don't understand why you need to check (pivot%3 != 0) while it is checked in getPivot() function.

taitung + 0 comments My answer to N = 1000 is 5555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555553333333333

you see there are 10 number 3 in this string.

sagemode + 3 comments yeah finding the pivot is important. My solution is similar. I aimed to remove the expensive operation "modulo", here's my solution.

`#Python solution without modulo t = int(input().strip()) for a0 in range(t): n = int(input().strip()) x = (int(n / 3)) * 3 y = 0 while True: y = n - x if ((int(y / 5)) * 5 != y): if (x == 0): print("-1") break x = (int((x - 1) / 3)) * 3 else: print (int(x) * "5" + int(y) * "3") break`

mdsmithson + 1 comment why are you putting a solution in the discussion?

gauraviitkgp + 0 comments [deleted]

gauraviitkgp + 0 comments [deleted]gauraviitkgp + 0 comments import sys can u telll me what is error in my code

t = int(raw_input())

test = 0

for a0 in xrange(t):

`n = int(raw_input().strip()) for i in range(0,n): if (n-5*i)>=0 and (n-5*i)%3==0: print("5"*(n-5*i)+"3"*(i*5)) test = test + 1 if test==0: print("-1")`

flowerking + 3 comments Downloaded and checked the test cases on local machine. And the answers correct but when submitted showing as incorrect!

thebick + 1 comment Apparently HackerRank is truncating all output after 32767 total characters (on all lines combined). Perhaps someone needs to check the output box to see what its limit is.

CattleOfRa + 1 comment my code consists of 600 characters, it's working perfectly fine on my local machine but gives me timeout here. What could be the issue?

CattleOfRa + 0 comments Nevermind. My algorithm was just too slow. I've managed to complete it now

changcw83 + 0 comments [deleted]dexxer + 1 comment I'm running into the same issue. Downloaded a few of the failed test cases only to find out that my algorithm actually works... lame!

wasihaiderdev + 0 comments Probably a performance issue...

Sort 398 Discussions, By:

Please Login in order to post a comment