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.
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
Sherlock and The Beast
You are viewing a single comment's thread. Return to all comments →
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.