We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

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

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

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.

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!

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!

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?

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.

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);
}
}
}

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.

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);
}

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

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

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.

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.

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

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.

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?

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.

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?

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.

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.

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

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!

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

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

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:

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.

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

## Sherlock and The Beast

You are viewing a single comment's thread. Return to all 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

You're my hero. Thanks for the tip!!

Thank you yeremy, appreciate the reply :)

Thanks for posting it.

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

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

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 ?

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

More specifically it is a Diophantine equation.

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?

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

linearDiophantine equation.so a linear equation is part of the set of Diophatine equations. Thanks! I didn't quite get that at first.

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.

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.

Thank you mang, appreciate the reply :)

test case not running properly

Try it again. It did for all of us.

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.

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

Great one, just simplisitc.

GENIUS!

Clever!

Thanks man. Helped me with my solution.

Its a great and simple solution. Thanks for tips.

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!

Thank you mmarques, appreciate the reply :)

br hu3hu3hu3

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!

Thank you isafa, appreciate the reply :)

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?

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.

Thanks a lot :-)

Psh...

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

Testing, comment didn't show up

If i input 7... It will decreese 10 .. then it will be a minus value..

awesome solution thanks a lot!!

do it in java aq

Works like a beast -->

doesnt work for n=11

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:

Can you explain the logic please?

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.

thanks for the feedback, nice thinking!

nice, this help me.

Thanx man , easy to understand

Excellent solution... @Dineshchv..

Why mix output logic with determination of x and y?

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

Here is my solution:-

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

Thanks man this help me a lot, i was confussed with that even it is not printing in eclipse also.

That string builder approach helped me too thanks for help!!

Can you explain the logic please?

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

I don't get it

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

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

The number of 3s are divisible by 5 and the number of 5s (which is 0) are divisible by 3.

I need to ask this, but how the number of 3s is divisible by 5 (33333 / 5 = 6666.6)? The result is not an integer.

number of 3s = 5 which is literally the number of 3s my friend.

Thank you, I understand this now. I have missed interpreted this. The number of digits should be divisible with 5 or 3.

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.

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

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

I posted detailed explanation lower.

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

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.

Best explanation i got for this question. Thanks a lot :-)

Sounds complicated. I just threw modulos at it until it worked. ;)

superb explanation !....

You're a goddamn wizard.

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

Wow, excellent and intuitive explanation, plus examples, plus a proof! Thanks!

Great explanation!

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

Thank you so much, elkapalka! This really made it clear for me.

thanks a lot.

thanx for this explanation!!

Thanks! It's a perfect explanation.

Thank you for your helping, I solved the problem.

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

After your explanation I have understood the question Tnx a lot

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

wow just clear as RO water.

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.

Thank you, this was very helpful!!

my test cases are ran out of time.

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

Don't know about another languages, sorry.

yeah,it did. Thanks.

This is because String is immutable and every concatination will create new object.

Awesome Solution. Thank you for the logic.

can you give your implemention ?

In every sense of the word, this solution is terse. Well done!

Your advice really helped me a lot reaching a solution :)

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?

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.

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?

Thank you very much theroadtaken123

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

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.

Thanks for trying

int main(){

}

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

same with me

changes to your code and its working for all test cases

int main(){

}

Why are you putting a solution in the discussion?

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

sallute!!

Thanks Man. This code is really helpful

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 {

}

what if the number is even??

Thannk you very much!!!

nice solution, thnx!

nice solution, thnx!

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

Superb solution !! thanks

What if the input is 10? we get wrong answer.

it works for input 10 as well you will get -1 as output.

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.

Hi theroadtaken123 where you able to runt he test cases ?

Great Solution....Thanks

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

Thanks! Very smart! :D

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

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

Really awesome technique. Hats off to you.

Simply Awesome :)

Thanks ;)

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.

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

}

Awesome bro! How did you reach to this solution?

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

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

This is the most simplistic, elegant and optimal solution.

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

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

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

Superb bro!!

_/_

i don't get it. can you explain in simpler way?

Thanks a lot. Great way ;)

C++ solution-->

how does this string(z.'5') work ?

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

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

9times; modulo 2: 5 needs to be subtracted3times. 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 numbercan notmathematically 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".

Only maths can do it!!.Thanks for the tip!!

getting terminated due to timeout plzz help

Java 8C++ solution :