# Sherlock and The Beast

# Sherlock and The Beast

theroadtaken123 + 70 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 + 0 comments [deleted]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.

maxiiminu + 1 comment I try in c++ and php, both dont work, and the error is "truncated", what i do?

victorliafook + 0 comments "truncated" basically means that your output is too large; So I would guess that you are outputting(printing) unnecessary stuff. Moreover I would guess that your code is getting into an infinite loop and printing stuff on and on and on.

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.

Richard19Perez77 + 1 comment DioPhantine is A * * 2 + b * * 2 = c * * 2 but this seems like A * x + B * x = C where x > 0 || y > 0 am i wrong to argue you on this?

TheZero + 1 comment A Diophantine equation is simply one in which we are only interested in integer solutions. This is known as a

*linear*Diophantine equation.Richard19Perez77 + 1 comment so a linear equation is part of the set of Diophatine equations. Thanks! I didn't quite get that at first.

TheZero + 0 comments The important part is that we're only interested in integer ("whole number") solutions. In this case, the Diophantine equation is

n = 5x + 3y

and we only care about cases where x and y are both integers. For example, if n were 11, we don't care about the solution x=1.6, y=1. We're only interested in the solutions like x=1, y=2.

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 :)

sharan183 + 1 comment test case not running properly

theroadtaken123 + 1 comment Try it again. It did for all of us.

peggyfan + 1 comment I tried the same codes but I get '-1' for the test case of N = 3. So what happens in the case of if N % 3 == 0? Sorry I might have missed something.

SoulReaver + 0 comments You copied it wrong; if else statement won't be inside the while...

Gurupad + 0 comments Great one, just simplisitc.

vishnumurali113 + 0 comments GENIUS!

ka1gu0 + 0 comments Clever!

Sumiibi + 0 comments Thanks man. Helped me with my solution.

sunilkv117 + 0 comments Its a great and simple solution. Thanks for tips.

mmarques + 2 comments Amazing! Very clever! I didn't account for the possibility of large numbers before, but your solution totally avoids the problem. It's impressive how such a simple problem can teach you important lessons. Thanks!

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

thalesfc + 0 comments br hu3hu3hu3

isafa + 1 comment Thank you for the explanation. This is by far the best tip I have come across. I was going in another direction because of the word permutation. You are my hero as well!

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

RTCoder + 1 comment What would happen if you did it the other way? Keep subtracting by 3 until it is divisible by 5? I am assuming that would be the method of solution if you needed a multiple of 5 for "5"'s and a multiple of 3 for "3"'s?

thakurdigvijay_1 + 2 comments But look at the problem carefully my dear friend we have to find the largest number, But if we do it other way around than no. if 3s will be more thn no. of 5s hence it wont be the largest n. of that type.

mkhan31995 + 0 comments Thanks a lot :-)

Ayelis + 0 comments Psh...

answer.split("").sort().reverse().join(""); //DONE

RTCoder + 0 comments Testing, comment didn't show up

Vidya_Jasud1 + 0 comments [deleted]Fazith + 0 comments If i input 7... It will decreese 10 .. then it will be a minus value..

shivam9544 + 0 comments awesome solution thanks a lot!!

pardonmydust4 + 2 comments do it in java aq

piyush121 + 4 comments Works like a beast -->

`public static void main(String[] args) { Scanner in = new Scanner(System.in); int t = in.nextInt(); for(int a0 = 0; a0 < t; a0++){ { int n = in.nextInt(); StringBuilder strb=new StringBuilder(); int j=0; for(int i=n;i>0;i--) { if(i%3==0 && (n-i)%5==0) { for(j=0;j<i;j++) strb.append("5"); for(int k=j;k<n;k++) strb.append("3"); break; } } if(strb.length()==0 && n%5==0) for(int k=n;k>0;k--) strb.append("3"); else if(strb.length()==0) strb.append(-1); System.out.println(strb); } } }`

savvy2411 + 0 comments doesnt work for n=11

DineshChv + 7 comments THANK YOU MAN This helped me a lot. I'm using String instead of StringBuilder or StringBuffer. Now I changed it to StringBuffer and my code ran faster than before :) This can still be reduced to:

`public static void main(String[] args) { Scanner in = new Scanner(System.in); int t = in.nextInt(); for(int a0 = 0; a0 < t; a0++){ { int n = in.nextInt(); StringBuilder strb=new StringBuilder(); for(int i=n;i>=0;i--) { if(i%3==0 && (n-i)%5==0) { int j=0; for(j=0;j<i;j++) strb.append("5"); for(int k=j;k<n;k++) strb.append("3"); break; } } if(strb.length()==0) System.out.println("-1"); else System.out.println(strb); } } }`

kpratik + 0 comments Can you explain the logic please?

kweic + 1 comment since your amount of 5s need to be divisible by 3 you can append "555" instead and tweak the count of your j in the loop to match, and the same for your 3s to get through the loop a little faster.

Richard19Perez77 + 0 comments thanks for the feedback, nice thinking!

jaydeep2990 + 0 comments nice, this help me.

sdrockzz06 + 0 comments Thanx man , easy to understand

sankireddyvinee1 + 0 comments Excellent solution... @Dineshchv..

martin89 + 0 comments Why mix output logic with determination of x and y?

Why use loops to build string (or Stringbuilder)? Obfuscates code.

Here is my solution:-

`static void decentNumber(int n) { int x = 0; int y = 0; for (int i = n; i >= 0; i--) { if (i % 3 == 0 && (n - i) % 5 == 0) { x = i; y = n - i; break; } } var res = y == 0 && x==0? "-1" : new string('5', x) + new string('3', y); Console.WriteLine(res); }`

mayurnagdev123 + 0 comments Using String instead of StringBuffer results in timeout for most test cases.I found out why- "Simply stated, objects of type String are read only and immutable. The StringBuffer class is used to represent characters that can be modified. The significant performance difference between these two classes is that StringBuffer is faster than String when performing simple concatenations."

kpratik + 1 comment Can you explain the logic please?

Zack_Knight + 1 comment 'the amount of 5s should be divisible by 3' and 'the amount of 3s should be divisible by 5'.Logic checks that i digits should be divisible by 3 and at the same time n-i digits should be divisible by 5.Here i or n-i can be zero also.

Richard_Khonan + 0 comments I don't get it

aurigaKG + 0 comments yes thanks, using StringBuilder instead of String gave away all timeout errors . Nice learning .

saif01md + 0 comments int n = in.nextInt(); int z=n; while(n%3 !=0){ n=n-5; } if(n<0){ System.out.println("-1"); } else{ StringBuilder sb=new StringBuilder(); for(int j=0;j

mos_alex + 1 comment [deleted]evanplaice + 0 comments You can use a much less 'clever' solution with a deterministic limit by pre-calculating the maximum product of integer division (ie floor) of input//3, input//5. It only uses 2 division operations. All the rest are multiplication. The slowest tests are .1s but Javascript isn't exactly optimized for raw calculation performance.

atomheart + 2 comments Can someone explain how this works? I don't understand how subtracting 5 "x" times makes the number a multiple of 3.

mkhan31995 + 0 comments hey can you please explain me the 4th property of the Decent Number shown...?

elkapalka + 0 comments I posted detailed explanation lower.

zshakked + 1 comment I am really having difficulty understanding this. Can someone give me an ELI5 explanation?

elkapalka + 17 comments I will try to explain. Bear with me :))

So, we have N numbers n_5 numbers of 5 and n_3 numbers of 3. n_5 + n_3 = N n_5 need to be divisible by 3 and n_3 need to be divisible by 5. Key to solving this task is that n_5 + n_3 need to be MAXIMUM from all exist cases. If you will think about this it’s easy to see that the maximum is then 5s in the beginning and 3s in the end (I hope this doesn’t need explanation) We will apply greedy algorithm principle: we need to take as much 5s in the beginning as we can. And only rest chunk of number fill with 3s. So now we have 2 cases from here: First one is trivial N is divisible by 3: N % 3 = 0. For example N is 9. Easy peasy: “555555555”

Second case when N is not divisible by 3. What does it mean for us? That we need to fill some positions with 3s starting from tail. As n_3 need to be divisible by 5. We fill with 5 3s, look if we satisfying our constraints or not, if not fill again with 5 3s. Example 1: N = 11 N%3 = 2. First fill all 11 position with 5s “55555555555”. Now start to replace it with “3” First time: “55555533333” Does it satisfy constraints? Yes it does. n_5 = 6 n_3 = 5.

Example 2: N = 10 N%3 = 1. First fill all 11 position with 5s “5555555555”. Now start to replace it with “3” First time: “5555533333” Does it satisfy constraints? Nope. n_5 = 5 and it’s not divisible by 3. So we fill with 3 3s again. “3333333333” Does it satisfy constraints now? Yes it does. n_5 = 0 n_3 = 10

If you will play with any examples you will see that no matter how long number you will take you need to fill with “3”s only one time or two times, no more. When remainder is 2 It will be 1 time. If remainder is 1 it will be 2 times. Why this is happening?? There are no woodoo magic here, no pins and no dolls. Let’s look closer:

Modulo 1: N%3 = 1 we can rephrase: x*3 +1 = N Now let’s start to fill with “3” x*3 +1 - 5 -> x*3 - 4 Is it divisible by 3? Nope. Let’s fill more 5 cells with 3s. x*3 +1 - 10 -> x*3 - 9 -> 3(x-3) Now we now that this is ALWAYS divisible by 3. So our answer is n_3 = 10, n_5 = N - 10

Modulo 2: N%3 = 2 we can rephrase: x*3 + 2 = N Now let’s start to fill with “3” x*3 +2 - 5 -> x*3 - 3 -> 3(x - 1) And it’s ALWAYS divisible by 3 So our answer is n_3 = 5, n_5 = N - 5

That’s it. Now don’t forget about cases then N is less than 10 and voila.

mkhan31995 + 0 comments Best explanation i got for this question. Thanks a lot :-)

Ayelis + 0 comments Sounds complicated. I just threw modulos at it until it worked. ;)

pranoysarath + 0 comments superb explanation !....

tgamerkle + 0 comments You're a goddamn wizard.

arkopal0111 + 0 comments Thank you very much for explaining. I had the logic in mind but wasnt able to execute it to generate result. Your Tip made it easier to approach the question. Thanks a ton

anglessteven + 0 comments Wow, excellent and intuitive explanation, plus examples, plus a proof! Thanks!

chrislam67 + 0 comments Great explanation!

Matthew_Ticciati + 0 comments Thank you! Very clear explanation for those of us with less of a mathematics background.

richbward + 0 comments Thank you so much, elkapalka! This really made it clear for me.

horiafx + 0 comments thanks a lot.

golugupta + 0 comments thanx for this explanation!!

ryashin_egor + 0 comments Thanks! It's a perfect explanation.

calmwaterfall + 0 comments Thank you for your helping, I solved the problem.

VeRa399 + 0 comments i'm cant pass few test cases although i have followed what you said. help?

`int n; cin >> n; if(n < 3 || n == 4 || n == 7) { cout << -1 << endl; continue; } if(n == 8) { cout << "55533333" << endl; continue; } if(n%3 == 0) { for(int i = 0; i < n; i++) cout << "5"; cout << endl; } else if(n%5 == 0) { for(int i = 0; i < n; i++) cout << "3"; cout << endl; } else if(n%3 == 2) { for(int i = 0; i < n-5; i++) cout << "5"; for(int i = n - 5; i < n; i++) cout << "3"; cout << endl; } else if(n%3 == 1) { for(int i = 0; i < n-10; i++) cout << "5"; for(int i = n-10; i < n; i++) cout << "3"; cout << endl; } else cout << -1 << endl;`

rejwancse10 + 0 comments After your explanation I have understood the question Tnx a lot

maheshvangala191 + 0 comments If i take stringbuilder it is solved why shouldn't i take string in place of stringbuilder plzz tell me

PAL_RAJAT1997 + 0 comments wow just clear as RO water.

Sourav242 + 0 comments if(z<0 and z!=0): print '-1' this is required I guess. but this simple code is showing timeouts and is unable to find out the ans for 99946. whereas 46/946/9946 are cool.

codyth + 0 comments Thank you, this was very helpful!!

yashpandya212 + 1 comment my test cases are ran out of time.

elkapalka + 1 comment If you use java and use String, switch to StringBuilder it will solve your problem.

Don't know about another languages, sorry.

yashpandya212 + 1 comment yeah,it did. Thanks.

elkapalka + 0 comments This is because String is immutable and every concatination will create new object.

m_saikiran + 0 comments Awesome Solution. Thank you for the logic.

jitendraiitd2000 + 0 comments can you give your implemention ?

tkhan14 + 0 comments [deleted]andrewmorris847 + 0 comments In every sense of the word, this solution is terse. Well done!

khaledahmedyoun1 + 0 comments Your advice really helped me a lot reaching a solution :)

narenprasad + 1 comment I loved it,but i want to know what made you to try this kind of logic if we need to do with 3,7 instead of 3,5 with respective rules. how can find logics for this kind of questions?

peterkirby + 0 comments You could just change the constants in this simple algorithm. A solution is guaranteed (for large enough numbers of digits) whenever the two constants are coprime (no common prime factors). If the problem merited it (larger constants), you could use the Extended Euclidean Algorithm to calculate, but that would require some understanding of modular arithmetic.

`numFives = numDigits - (numDigits % 3); numThrees = numDigits - numFives; while (numThrees % 5) numThrees += 3; numFives = numDigits - numThrees;`

apprajapati + 0 comments This is indeed a best solution for this problem, but is there anyone who can explain why this correlation exists between reminder and amount of subtraction?

Mumthas_43 + 0 comments Thank you very much theroadtaken123

AnuragPatil + 1 comment Thank you very much for sharing the logic. I tried implementing it using cpp. Working fine for small cases.

int main(){ int t; cin >> t; for(int a0 = 0; a0 < t; a0++){ int n, y, z, flag = -1; cin >> n; z = n; if(z <= 0) cout<<"-1\n"; else { if(z%3 == 0) { cout<< string(z,'5')<<"\n"; } while(z%3 != 0) { z -= 5; if(z<0) { cout<<"-1\n"; break; } else { cout <

But it prints some crap for cases like 100,121,etc Did i messed some thing with your logic?? Any suggestions plz. Thank you ...

Richard19Perez77 + 1 comment I am not sure, did you check my solution in Java, I am sure you have access to my solutions? Sorry I am not very skilled in C++, I have worked only with C# and Java for the last 3 years.

AnuragPatil + 2 comments Thanks for trying

int main(){

`int t; cin >> t; for(int a0 = 0; a0 < t; a0++){ int n, y, z, flag = -1; cin >> n; z = n; if(z <= 0) cout<<"-1\n"; else { if(z%3 == 0) { cout<< string(z,'5')<<"\n"; } while(z%3 != 0) { z -= 5; if(z<0) { cout<<"-1\n"; break; } else { cout<<string(z,'5')<<string((n-z),'3')<<"\n";; } } } } return 0;`

}

This is what i ment exactly, but still not working for large inputs :(

achyuthreddy_15 + 0 comments same with me

sanchitpatiyal95 + 1 comment changes to your code and its working for all test cases

int main(){

`int t; cin >> t; for(int a0 = 0; a0 < t; a0++) { int n, y, z, flag = -1; cin >> n; z = n; if(z <= 0) cout<<"-1\n"; else { if(z%3 == 0) { cout<< string(z,'5')<<"\n"; } while(z%3 != 0) { z -= 5; if(z<0) { cout<<"-1\n"; break; } else { if(z%3==0) cout<<string(z,'5')<<string((n-z),'3')<<"\n"; } } } } return 0;`

}

Astrodynamic + 0 comments #include <bits/stdc++.h> using namespace std; int main(void) { int t; cin >> t; for (int i = 0; i < t; i++) { int n, z; cin >> n; z = n; if(z % 3 == 0) { cout << string(z, '5') << endl; } while(z % 3 != 0) { z -= 5; if(z < 0) { cout<< "-1" << endl; break; } else { if(z % 3 == 0) cout << string(z, '5') << string((n - z), '3') << endl; } } } return 0; }

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

desi_duuh + 0 comments So we aren't stuck in a solution for ever and actually learn and move on with life my good sire. .

i5pranay + 0 comments sallute!!

i_AnkurBiswas + 0 comments Thanks Man. This code is really helpful

claire16 + 0 comments I didn't pass the last 2 test cases and got a run time error for the last test case. Could anyone find the bug in my solution?

import java.io.

*; import java.util.*;public class Solution {

`public static void main(String[] args) { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); String out = ""; while(T-- > 0) { int key = sc.nextInt(); if(key % 3 == 0) { out = new String(new char[key]).replace("\0", "5"); } else { int x = key; while(x % 3 != 0 && x > 0) { x -= 5; } if(x%3 == 0) { String fives = new String(new char[x]).replace("\0", "5"); String threes = new String(new char[key-x]).replace("\0", "3"); out = fives+threes; } else if(x == 0) { out = new String(new char[key]).replace("\0", "3"); } else out = "-1"; } System.out.println(out); } }`

}

revantt + 0 comments what if the number is even??

Fazith + 0 comments Thannk you very much!!!

tomararyan11 + 0 comments nice solution, thnx!

tomararyan11 + 0 comments nice solution, thnx!

nitmnit + 0 comments Sorry, I still don't get why you chose to subtract from 5? Please explain.

Saibabagajula + 0 comments Superb solution !! thanks

aliciaflinchum + 0 comments I'm confused about 4. How would this work for 4? z%3 would not equal 0 but z-=5 would be -1. I could understand how it could work for all other cases I can think of.

abhishekramkumar + 0 comments Hi theroadtaken123 where you able to runt he test cases ?

Tushar1111 + 0 comments Great Solution....Thanks

maxiiminu + 0 comments I try in c++ and php, both dont work, and the error is "truncated", what i do?

RashikaSharma + 0 comments Thanks! Very smart! :D

Bob_Roebling + 0 comments Extension for Swift to multiply Strings/Characters. Don't forget to unwrap the optional.

extension String { public init?(byRepeatingString str: String, count: Int) { var newString = "" for _ in 0 ..< count { newString += str } self.init(newString) } }

thnguyen24 + 0 comments You don't need while loop. You only need 2 iterration because z%3 = (z-15)%3, (z-5)%3 = (z-20)%3, ...

Nipunroyal + 0 comments Really awesome technique. Hats off to you.

SOUMYABRATA + 0 comments Simply Awesome :)

emanuel_feijo9 + 0 comments Thanks ;)

doanhuunoi + 0 comments this is the best solution. try to find the largest number of digits which is divided by 3 and put corresponding number 5 at the begin of result.

aladil2605 + 0 comments this is an old discussion but is there any suggestions about this sol in c /**/ void repeat_char(char c , int co ) { for (int i=0; i < co; i++ ) { printf("%c", c); } } int main(){ int t; scanf("%d",&t); int n[t]; for(int a0 = 0; a0 < t; a0++){ scanf("%d",&n[a0]); } for(int a0 = 0; a0 < t; a0++){

int num5 = n[a0] - n[a0] %3; int num3 = n[a0] - num5; switch(num3 % 5){ case 1: num3 = 10;break; case 2: num3 = 5;break; case 3: num3 = 15;break; case 4: num3 = 10;break; } if(num3>n[a0]){ printf("-1\n");

continue; } num5 = n[a0] - num3; if(num5>0) repeat_char('5',num5); if(num3>0) repeat_char('3',num3); printf("\n");`} return 0;`

}

jain01ankur + 0 comments Awesome bro! How did you reach to this solution?

shash95 + 0 comments Hey guys, can someone please help me out as to why this is not working? Would appreciate any help. Thanx.

`public static void main(String[] args) { Scanner in = new Scanner(System.in); int t = in.nextInt(); for(int a0 = 0; a0 < t; a0++){ int n = in.nextInt();int m; String x=""; if(n%3==0){ for(int i=0;i<n;i++){ x=x+"5"; } System.out.println(Long.parseLong(x)); } else{ for(m=n;m%5!=0;){ m=m-3; if(m<0) break; } if(m<0){ System.out.println(-1); continue; } else{ for(int i=m;i<n;i++){ x=x+"5"; } for(int i=0;i<m;i++){ x=x+"3"; } System.out.println(Long.parseLong(x)); } } } }`

RobertsN + 2 comments No need for repeated subtractions or loops. It's purely O(1) (just straightforward formula split in two parts, two calculations).

int q = ((3-(N%3))%3) *5; if (N-q < 0) cout << -1 << endl; else cout << string(N-q,'5') << string(q,'3') << endl;

chava_jauregui + 0 comments This is the most simplistic, elegant and optimal solution.

ggorlen + 1 comment I didn't downvote since this is a perfectly fine answer, but are you sure

`string()`

isn't using a loop under the hood? The solutions using a while loop in these examples will only iterate twice at most, which is O(1). Solutions on this page are pretty much all O(n) because of the string multiplication loops which are the most expensive part of the function. Correct me if I'm mistaken!RobertsN + 1 comment I've no idea how the string constructor is built under the hood. From the user code perspective it is O(1). Likewise many other solutions when written in Python or other higher level languages probably do have hidden loops in the language implementation. BTW someone else did downvote (not that I really care) but didn't say why...

ggorlen + 1 comment O(1) means that this method runs just as fast on

`n = 1,000,000,000`

as it does on`n = 10`

, which isn't the case. The string multiplication is the performance bottleneck causing the algorithm to be O(n) rather than O(1). Here's some test code showing that the code is O(n) due to the`string()`

call (I'm not a C++ programmer, so pardon any mistakes):#include <ctime> #include <iostream> #include <sstream> using namespace std; void sherlock(int N) { clock_t begin = clock(); int q = ((3-(N%3))%3) *5; if (N-q < 0) { cout << -1 << endl; } else { std::stringstream buffer; buffer << string(N-q,'5') << string(q,'3') << endl; } clock_t end = clock(); cout << double(end - begin) << endl; } int main() { cout << "N = 5: "; sherlock(5); cout << "N = 100000000: "; sherlock(100000000); return 0; } /* gcc version 4.6.3 N = 5: 29 N = 100000000: 143633 */

My main point is that a lot of folks are mistakenly assuming the while loop solution is not O(1). The loop in this case is O(1) because regardless of how large

`n`

is, the loop body will never execute more than twice at most, so from an efficiency standpoint there is no difference as advertised. See the below code:#include <ctime> #include <iostream> #include <sstream> using namespace std; void sherlock(int N) { clock_t begin = clock(); int t = 0; while (N % 3 != 0) { N -= 5; t += 5; } std::stringstream buffer; buffer << string(N, '5') << string(t, '3') << endl; clock_t end = clock(); cout << double(end - begin) << endl; } int main() { cout << "N = 5: "; sherlock(5); cout << "N = 100000000: "; sherlock(100000000); return 0; } /* gcc version 4.6.3 N = 5: 18 N = 100000000: 109843 */

amdokamal + 0 comments You are right, there is a but. The author of Editorial and other people simply neglect "multiplying strings" and other operations because the performance difference in comparison with the Sherlock algorithm O(1) is extremely small at the level of 1 <= n <= 100000.

hjalmar_basile + 0 comments There's no need of the while loop anyway, search for my solution down below.

akshay_k13 + 0 comments Superb bro!!

saif01md + 0 comments _/_

Richard_Khonan + 0 comments i don't get it. can you explain in simpler way?

deepjyot33 + 0 comments Thanks a lot. Great way ;)

ashishTrivedi16 + 0 comments [deleted]ashishTrivedi16 + 1 comment C++ solution-->

#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> using namespace std; int main() { int t, n, flag = 0; cin >> t; for(int i = 0; i < t; i++){ cin >> n; int z = n; while(z % 3 != 0){ z -= 5; if(z < 0){ cout << "-1" << endl; flag++; break; } } if(flag == 1){ flag = 0; }else{ cout << string( z, '5') << string( n-z, '3') << endl; } } return 0; }

kman30 + 1 comment how does this string(z.'5') work ?

ashishTrivedi16 + 0 comments in string(x, 'y') x is the number of times tou want to repeat a particular character and y is the character to be repeated

gnemlock + 0 comments The theory your running is close. I think you mis-explain it, given that you actually passed the test cases.

modulo 1: 5 needs to be subtracted

**9**times; modulo 2: 5 needs to be subtracted**3**times. Remember, 5 needs to appear a number of times divisible by 3. If the current number is divisible, and you remove 1 or 2, the resulting number*can not*mathematically be divisible by 3.You also need to add an additional check to make sure that you actually have enough 5s to remove the required number. If not, that should be the only case where you can not make a proper number, resulting in a "-1".

spg1997 + 0 comments Only maths can do it!!.Thanks for the tip!!

maheshvangala191 + 0 comments getting terminated due to timeout plzz help

sameerjadhavweb + 0 comments **Java 8**static String aDecentNumber(int n) { int temp = n; while (temp >= 3) { if (temp % 3 == 0) { return fillNo(5, temp) + fillNo(3, n - temp); } temp -= 5; if (temp == 0) { return fillNo(3, n); } } return "-1"; } static String fillNo(int no, int times) { StringBuffer sb = new StringBuffer(); for (int i = 0; i < times; i++) { sb.append(no); } return sb.toString(); }

AntonDeCode + 15 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 :')

igormartire + 0 comments Thanks!!

LeMasque + 0 comments Wow, thank you for your comment. I spent like 5 hours or so messing with my code before coming here and finding this comment. I had tried finding larger strings to try to append together (e.g. adding three 5's at a time versus one 5) and that made it faster but not enough. But then you enlightened me, thank you so much.

arsho + 0 comments That was very helpful! But I didnot use StringBuilder. I printed the numbers inside loop and printed a new line after the loop.

rockyli + 0 comments Solved my timeout problem. Thank you!

ramendu + 0 comments Thanks a lot, solved my timeout issue! Here is a virtual cookie for you! :D

Cookie cookie = new Cookie("thanks","please have this cookie"); HttpServletResponse tummy = new HttpServletResponse(); tummy.add(cookie);

marcelosedano + 0 comments StringBuilder saved my marriage and helped my kids get through college. Thank you StringBuilder!

yashpandya212 + 0 comments Thanks.My test cases are now accepted.

ArkhamDriver + 0 comments String appending indeed is a problem, string builder is so much better, thanks for your tip!

SergioGM + 0 comments Hey man, I didnt know how StringBuilder worked, but still got the solution reducing the number of iterations.

`public static void main(String[] args) { Scanner in = new Scanner(System.in); int t = in.nextInt(); for (int i=0;i<t;i++){ int n = in.nextInt(); String sol3 = "", sol5 = ""; String staux = "555"; while(n>0){ if (n%3==0) break; else{ sol3+="33333"; n-=5; } } while (n>0){ if (staux.length()<=n){ sol5+=staux; n-=staux.length(); staux+=staux; } else if (n<3) break; else staux="555"; } if (n==0) System.out.println(sol5+sol3); else System.out.println(-1); } }`

Still much better using Stringbuilder, but not impossible with strings ;) Thanks for the info.

Weemus + 0 comments Same tip for the C# crowd. Strings are immutable; go with the StringBuilder

liewsanmin + 0 comments hahah nice ad..

Soul_XHacker + 0 comments Same for C#. I just wasted 1 hour by doing string concatenations and getting timeouts. Honestly man, even after learning string theory a dozen times, I still forget that strings are immutable.

Thanks man.

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?

asbear + 1 comment Missed the new O(1) solution was added while the complexity on the right side was still O(N)

gaggio23 + 1 comment While the time spent to compute the number of threes and fives to print is well reduced, you still have to print N digits, so technically the complexity still is O(n).

AntonDeCode + 0 comments [deleted]

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")`

Kamijo_Haytham + 0 comments Can someone please explain the code for me especially the "getPivot" function? I don't get it...

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...

hobbes0 + 1 comment A bit of pseudo code below on how I solved this. The trick, really, is to just analyse the input numbers and to avoid actually generating the final answer until the end. Hopefully this will help those of you who are stuck:

*Let's look at two numbers: the numbers of fives (F) and the number of threes (T). For the purposes below "n" will be the inputted number length.*The default biggest number will be one consisting of all 5s, so lets start out with F = n and T = 0. So our number right now consists of all 5s and no 3s.

Is the number compliant? Test: F is a multiple of 3 and T is a multiple of five. Answer: If Yes:

**return F and T**, BUT IF No:We need to replace some 5s with 3s, and since the 3s must be in multiples of 5, we need to reduce F by 5 and increase T by 5, so: F = F - 5 and T = T + 5.

After we decrease F, is it less than zero? If so, we have a bad number and we can

**return -1**. IF NOT:Lets recursively run through our steps again, and jump back to step #2, and continue doing so until we hit one of our two return conditions.

*Once we've hit a return statement in the above, we just need to use the numbers either -1 or F and T, to generate a print statement.*Kronolynx + 0 comments thanks that was really helpful :)

BSathvik + 1 comment it looks like java cannot print a 100000 char string in one shot(i know that the string is printed but its just not visible and therefore cannot be read by hackerrank).if i loop the printing statement and print on the same line then hackeerrank doesnt accept my answer although the output is the same. it makes sense because i am executing multiple print stements for the same input. how do i solve this ?0-3 test are correct 4-13 always "Time out" and 14 is a runtime error(I'll look into it after i fix this :))and the 15 test is corrent.

`import java.io.*; import java.util.*; public class Solution { public static void main(String[] args) { Scanner in = new Scanner (System.in); int number = in.nextInt(); int temp=0; String s= ""; for (int i=0;i<number;i++){ temp = in.nextInt(); int five =temp; int three =0; s=""; for(int j =0;j<temp;j++){s+="5";} for (int k=0;k<temp;k++){ if (temp%3!=0&five%3!=0&temp>=5&five>0){ three+=5; five-=5; }else{break;} } if (temp>=3&five%3==0){ s=s.substring(0,five); for(int j=0;j<three;j+=5){ s+="33333"; } System.out.println(s); }else{System.out.println("-1");} } } }`

udaymittal + 2 comments I'm also getting 5-13 test cases as time-outs. Did you figure out what is causing the problem?

udaymittal + 1 comment Anyway, solved it. :) I was using an inefficient way to generate the number.

irohitsinghal + 2 comments `public static void main(String[] args) { // TODO Auto-generated method stub Scanner in = new Scanner(System.in); int tc = in.nextInt(); while (tc-- > 0) { getNumbr(in.nextInt()); } in.close(); } private static void getNumbr(int n) { // TODO Auto-generated method stub int n5 = 0, n3 = 0; int nt = n; while (nt % 3 != 0) { nt -= 5; n3 += 1; if (nt < 3 && nt != 0) { System.out.println("-1"); return; } } n5 = nt / 3; String s = ""; for (int i = 0; i < n5; ++i) s += "555"; for (int i = 0; i < n3; ++i) s += "33333"; for (int i = 0; i < s.length(); ++i) System.out.print(s.charAt(i)); System.out.println(); }`

could you please point out the inefficiency in printing in my case, as i am also getting timeout for 5-13.

udaymittal + 1 comment Use Arrays.fill() to generate the number instead of running a loop to genereate the number.

jagan722 + 0 comments We could do something like this as well

new String(new char[n]).replace('\0', '5');

This is to repeat character '5', number of times

zhaolongzhong + 0 comments use StringBuffer instead of "s+="

wyrlvillazorda + 0 comments use StringBuilder or StringBuffer...and also BufferedReader for input,...

mcotse + 3 comments Loops are very unnecessary in this problem, here is the more elegant way

a=int(raw_input('')) for i in range(0,a): n=(int(raw_input(''))) if n%3==0 and n!=0: print n*str(5) elif n%3==1 and n>=10: print (n-10)*str(5)+10*str(3) elif n%3==2 and n>=5: print (n-5)*str(5)+5*str(3) else: print '-1'

AntFitch + 0 comments Nice!!!

liewsanmin + 1 comment what's the java version of this?

sxffff + 0 comments import java.io.

*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*;public class Solution {

`public static void main(String[] args) { Scanner in = new Scanner(System.in); int t = in.nextInt(); for(int a0 = 0; a0 < t; a0++){ int n = in.nextInt(); StringBuffer sb = new StringBuffer(); if (n%3==0) { System.out.println(append(n,"5")); } else if (n%3==1) { if (n<10) { System.out.println("-1"); } else { System.out.println(append(n-10,"5") + (append(10,"3"))); } } else if (n%3==2) { if (n<5) { System.out.println("-1"); } else { System.out.println(append(n-5,"5") +(append(5,"3"))); } } } } private static String append(int numberOfTimes , String value){ StringBuffer sb = new StringBuffer(); for (int i = 0; i < numberOfTimes; i++) { sb.append(value); } return sb.toString(); }`

}

ktleary + 0 comments A not as pretty JS version:

`if (n%3==0 && n!=0) { console.log( Array(n+1).join("5")); } else if (n%3==1 && n>=10) { console.log(Array((n-10)+1).join("5")+Array(10 + 1).join("3")); } else if (n%3==2 && n>=5){ console.log(Array((n-5)+1).join("5") + Array(5+1).join("3")); } else { console.log('-1'); }`

isloat + 0 comments 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.

olof_salberger + 1 comment My solution in Python 3:

#!/bin/python3 import sys t = int(input().strip()) for a0 in range(t): n = int(input().strip()) k0 = 6*n % 15 k = k0 + 15*((n-k0)//15) print( "-1" if k0 > n else k*"5" + (n-k)*"3" )

abhaypandey0012 + 1 comment can you explain the logic behind it

olof_salberger + 1 comment Clearly, the largest decent number will have all the 5's first, and all the threes last, so we really just need to compute the number of 3's and 5's in the largest number.

You can do this by writing up the problem as a system of linear diophantine equations. if x is the number of 5s, and y is the number of 3s, we have the following constraints:

- x + y == n
- x % 3 == 0
- y % 5 == 0

which can be rewritten as:

- x % 3 == 0
- x % 5 == n % 5

one solution to this is to plug in x = 6n as a solution. If you have one solution, all other solutions are related to the one you have by multiples of 15 (try proving this yourself by looking at the difference between two solutions). So I pick the solution with the largest number of 5s.

abhaypandey0012 + 0 comments **Thankyou**I got it

Sort 337 Discussions, By:

Please Login in order to post a comment