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.
Hi! First we must realize that adding to all but the chosen one is the same as subtracting from only the chosen one.
Then the other idea is that we must find the optimal solution.
For example, 0 4 4 could be solved like this:
0 4 4 -->
0 4 2 -->
0 4 0 -->
0 2 0 -->
0 0 0 -->
But the optimal solution is this:
0 4 4 -->
0 4 -1 -->
0 -1 -1 -->
-1 -1 -1 -->
This is what I call the 'base'. and I add it to the delta, and it turns out you have to make at least 3 trials. Hope this helps.
Thanks for reply..sorry i coulndt get why we are adding that base to difference between two elements. and then dividing and Module operations. May be i am slow to get all this. Thanks for the reply.
Hi Partha, dont make low of your self. Whenever you dont get it take a small example. I will try to help with one.
consider 2,x; The main thing you want to do is make a singleton( or the minimum posssible number of) choice per a candidate.
a)If differnce between x and 2 is 5:
-adding 0 makes it divisble by 5. (you only made one choice on x).
-adding 1 or 2 makes it you to have more number of choices.
b)If differnce between x and 2 is 4:
-adding 1 makes it divisble by 5. (you only made one choice on x).
-adding 0 or 2 makes it you to have more number of choices.
c)If differnce between x and 2 is 3:
-adding 2 makes it divisble by 5. (you only made one choice on x).
-adding 0 or 1 makes it you to have more number of choices.
d)If differnce between x and 2 is 2:
-adding 0 makes it divisble by 2. (you only made one choice on x).
-adding 1 or 2 makes it you to have more number of choices.
e)If differnce between x and 2 is 1:
-adding 0 makes it divisble by 1. (you only made one choice on x).
-adding 1 or 2 makes it you to have more number of choices.
f)If differnce between x and 2 is 6:
-adding 1 makes it divisble by 5. (you only made two choices on x, first divide by 5 then reminder by divided 2). //same number of choices in this case even by adding 0.
-adding 2 makes it you to have more number of choices.
So for every candidate you add some base (0 or 1 0r 2) and consider the only the base that gives you minimum choices.
But why I need add some base?
A basic divisibility exaple. 9 is not perfectly divisible 5 but adding 1 to 9 makes it 10 and now perfectly divisble by 5.
But why base only till 0,1,2 and not more than 2?
if the diffence between x and y is:
a)4 adding 1 is div by 5
b)3 adding 2 is div by 5
c)2 it is div by 2
d)7 is div by 5 followed by 2
e)8 adding 2 is div by 5 followed by 2
f)9 adding 1 is div by 5 followed by 2
Did you observe the base is cycling around 0,1,2.so you never need not go beyond 2
This is a perfect explaination of adding base and finding the best case the logic except base addition would get you clear some test cases by the reducing approach but you would definitely need to add base so that you get the best apporach out of the three possible solutions. Good approach rohit! Thank You
Great stuff here, Lovealmgren. I plan to use a version of this algorithm myself.
Why exactly three bases, no more and no less? Why not two, or four?
If I had to guess, I'd suspect you found out through empirical testing -- add 1 to base in the loop until all test cases pass. That would work -- but is there a more formal mathematical explanation for your solution?
Looks the question is changed from using {5, 2, 1} to {5, 3, 1}, so we might need to change the number value in above code. Otherwise given input {2, 2, 5, 7}, it will give answer 3, but it could be 2.
But the test cases are not updated, so this answer will pass all test cases.
One more comment, we just need to concern about base in [0: 4], as if base is 5, there will be definitely one more operation needed.
Additional comment for clarity. The bases are there because adding to all but the chosen one is not completely the same as subtracting from only the chosen one. (Not until we consider adding the bases 0, 1, 2).
For example, to elaborate on the given example, if we had 0 4 4, under the division of (int)delta / 5 + delta % 5 / 2 + delta % 5 % 2 / 1 without bases, we technically cannot account for the option of -5 because we can't apply that to the number delta 4 (or if delta = 3 for that regard). Try running through delta = 4 on your own and you'll see what I mean.
Adding +1 (or +2 for delta = 3) here would fix that problem. We only need bases 0, 1, 2 to account for delta = 3 or 4. Once delta = 2, the superior choice would be to -2 and not -5, so we don't need additional bases.
My solution is similar to yours but it is not able to pass the last test case... its giving wrong result for a few sets. Can you please help me understand what I did wrong.
importjava.io.*;importjava.util.*;importjava.text.*;importjava.math.*;importjava.util.regex.*;publicclassMain{publicstaticvoidmain(Stringargs[])throwsException{/* Enter your code here. Read input from STDIN. Print output to STDOUT */Scannersc=newScanner(System.in);intt=sc.nextInt();intn;intq1=0,q2=0,r1=0,r2=0;intsum=0;intlow;for(intai=0;ai<t;ai++){n=sc.nextInt();int[]a=newint[n];for(inti=0;i<n;i++){a[i]=sc.nextInt();}sum=0;intk=0;longsum1=1000000000;Arrays.sort(a);low=a[0];for(low=a[0];low>=0;low--){sum=0;for(inti=0;i<n;i++){k=a[i]-low;//System.out.println(low + " " + a[i]);q1=k/5;r1=k%5;q2=r1/2;r1=r1%2;sum=sum+r1+q2+q1;//System.out.println(a[i] + "---" + q1 + " " + q2 + " " + r1);}//System.out.println(sum + "");if(sum<sum1)sum1=sum;}System.out.println(sum1);}}}
Equal
You are viewing a single comment's thread. Return to all comments →
100% correct Java 8 Solution
import java.io.; import java.util.;
public class Solution {
}
Thanks for sharing this. Could you please help me in understanding in the below logic. I didnt understand what we are doing here.
for(int base = 0; base < 3; base++) { int current_sum = 0; for(int i = 0; i < cookies.length; i++) { int delta = cookies[i] - cookies[0] + base; current_sum += (int)delta / 5 + delta % 5 / 2 + delta % 5 % 2 / 1; } sum = Math.min(current_sum,sum); }
Hi! First we must realize that adding to all but the chosen one is the same as subtracting from only the chosen one.
Then the other idea is that we must find the optimal solution. For example, 0 4 4 could be solved like this: 0 4 4 --> 0 4 2 --> 0 4 0 --> 0 2 0 --> 0 0 0 -->
But the optimal solution is this: 0 4 4 --> 0 4 -1 --> 0 -1 -1 --> -1 -1 -1 -->
This is what I call the 'base'. and I add it to the delta, and it turns out you have to make at least 3 trials. Hope this helps.
Thanks for reply..sorry i coulndt get why we are adding that base to difference between two elements. and then dividing and Module operations. May be i am slow to get all this. Thanks for the reply.
Hi Partha, dont make low of your self. Whenever you dont get it take a small example. I will try to help with one.
consider 2,x; The main thing you want to do is make a singleton( or the minimum posssible number of) choice per a candidate. a)If differnce between x and 2 is 5: -adding 0 makes it divisble by 5. (you only made one choice on x). -adding 1 or 2 makes it you to have more number of choices. b)If differnce between x and 2 is 4:
c)If differnce between x and 2 is 3:
-adding 2 makes it divisble by 5. (you only made one choice on x).
-adding 0 or 1 makes it you to have more number of choices.
d)If differnce between x and 2 is 2:
-adding 0 makes it divisble by 2. (you only made one choice on x). -adding 1 or 2 makes it you to have more number of choices. e)If differnce between x and 2 is 1:
-adding 0 makes it divisble by 1. (you only made one choice on x).
-adding 1 or 2 makes it you to have more number of choices.
f)If differnce between x and 2 is 6:
-adding 1 makes it divisble by 5. (you only made two choices on x, first divide by 5 then reminder by divided 2). //same number of choices in this case even by adding 0.
-adding 2 makes it you to have more number of choices.
So for every candidate you add some base (0 or 1 0r 2) and consider the only the base that gives you minimum choices.
But why I need add some base?
A basic divisibility exaple. 9 is not perfectly divisible 5 but adding 1 to 9 makes it 10 and now perfectly divisble by 5.
But why base only till 0,1,2 and not more than 2?
if the diffence between x and y is:
a)4 adding 1 is div by 5
b)3 adding 2 is div by 5
c)2 it is div by 2
d)7 is div by 5 followed by 2
e)8 adding 2 is div by 5 followed by 2
f)9 adding 1 is div by 5 followed by 2
Did you observe the base is cycling around 0,1,2.so you never need not go beyond 2
Thanks for your encouragement and support Rahul. I am slowly getting there.
This is a perfect explaination of adding base and finding the best case the logic except base addition would get you clear some test cases by the reducing approach but you would definitely need to add base so that you get the best apporach out of the three possible solutions. Good approach rohit! Thank You
Great stuff here, Lovealmgren. I plan to use a version of this algorithm myself.
Why exactly three bases, no more and no less? Why not two, or four?
If I had to guess, I'd suspect you found out through empirical testing -- add 1 to base in the loop until all test cases pass. That would work -- but is there a more formal mathematical explanation for your solution?
@lovealmgren can u please explain the idea of taking base with only 0,1 and 2?
Looks the question is changed from using {5, 2, 1} to {5, 3, 1}, so we might need to change the number value in above code. Otherwise given input {2, 2, 5, 7}, it will give answer 3, but it could be 2. But the test cases are not updated, so this answer will pass all test cases. One more comment, we just need to concern about base in [0: 4], as if base is 5, there will be definitely one more operation needed.
Additional comment for clarity. The bases are there because adding to all but the chosen one is not completely the same as subtracting from only the chosen one. (Not until we consider adding the bases 0, 1, 2).
For example, to elaborate on the given example, if we had 0 4 4, under the division of (int)delta / 5 + delta % 5 / 2 + delta % 5 % 2 / 1 without bases, we technically cannot account for the option of -5 because we can't apply that to the number delta 4 (or if delta = 3 for that regard). Try running through delta = 4 on your own and you'll see what I mean.
Adding +1 (or +2 for delta = 3) here would fix that problem. We only need bases 0, 1, 2 to account for delta = 3 or 4. Once delta = 2, the superior choice would be to -2 and not -5, so we don't need additional bases.
Your solution is O(n*log n) because of sorting. To make it O(n) just find minimum with linear search without sorting.
Yes you are right! Thx
Its not showing correct answer
int delta = cookies[i] - cookies[0] + base; current_sum += (int)delta / 5 + delta % 5 / 2 + delta % 5 % 2 / 1;
hai i am not understanding the delta is the adding element or not.
My solution is similar to yours but it is not able to pass the last test case... its giving wrong result for a few sets. Can you please help me understand what I did wrong.