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.

public static int findutil(int a[],int n,int min)
{
int count = 0;

for(int i=0;i<n;i++)
{
int temp = a[i] - min;
count+= temp/5;
count+= temp%5/2;
count+= temp%5%2;
}
return count;
}
public static int find(int a[],int n,int min)
{
int res=Integer.MAX_VALUE;
for(int i=0;i<5;i++)
res = Math.min(res,findutil(a,n,min-i));
return res;
}
public static void main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
Scanner in = new Scanner(System.in);
int t = in.nextInt();
for(int i=0;i<t;i++)
{
int n = in.nextInt();
int a[] = new int[n];
int min = Integer.MAX_VALUE;
for(int j=0;j<n;j++)
{
a[j] = in.nextInt();
min = Math.min(min,a[j]);
}
System.out.println(find(a,n,min));
}
}

here, we have to equalize the number of chocolates that each person has. I have categorized the solution into four steps -

1> first thing you have to understand is that giving some chocolates to everyone except one is same as taking away chocolates from one of them. for example -
Out of 4 people in a competition,3 gets selected for next round --> 1 person loses.
Out of 4 people in a competition, 1 person loses --> 3 gets selected for next round.

2> Using the set of numbers which are given in the question (1,2,5), we can reduce any given value(say 201) to any desired value(say 0,10,37,99....upto 200).So, logically, we would want to reduce the rest of the numbers in the array to the minimum value in it and calculate the number of steps.

3>Now,we require the minimum number of steps, so for every element in array,first we will find the difference between the minimum value in array with the current element and divide it by 5(start with largest number in the set to smallest), then the remainder is divided by 2 and then by 1 and count the number of steps.

2 2 3 7 --> 2 2 2 7 --> 2 2 2 2 (2 steps)

4>But, here comes the tricky part. lets say the input is -
3 6 6.
Based on our logic,
3 6 6 --> 3 4 6 --> 3 3 6 --> 3 3 4 --> 3 3 3 (4 steps)

but, there is another minimal way
3 6 6 --> 1 6 6 --> 1 1 6 --> 1 1 1 (3 steps)

So, we will have to check for all the values (min,min-1,min-2,min-3 and min-4) to find out the best possible solution out of all the options.

Best possible solution can be found from (min,min-1,min-2). I think we don't need to check for (min-3) and (min-4). I have submitted by calculating optimal from (min,min-1,min-2). Can you provide an example where min-3 or min-4 is more optimal ?

My code :

#include<bits/stdc++.h>usingnamespacestd;intmain(){intt,n;cin>>t;while(t--){cin>>n;intarr[n],i,op1=0,op2=0,op3=0,mn=10000,left;for(i=0;i<n;i++){cin>>arr[i];if(mn>arr[i])mn=arr[i];}for(i=0;i<n;i++){left=arr[i]-mn;// for (min)op1+=left/5;left%=5;op1+=left/2;left%=2;op1+=left/1;left=arr[i]-(mn-1);// for (min-1)op2+=left/5;left%=5;op2+=left/2;left%=2;op2+=left/1;left=arr[i]-(mn-2);// for (min-2)op3+=left/5;left%=5;op3+=left/2;left%=2;op3+=left/1;}op1=min(op1,op2);// optimal from min-1 and min-2cout<<min(op1,op3)<<endl;// Most Optimal}}

generally, in dp solution..we start with 1 and build up our solution till n..but i think here (min,min-1,min-2) will do. how did you conclude that we dont require min-3,min-4. Can you elaborate

6 9 9 => reduce 9 to 6 in Two Steps + reduce next 9 to 6 in Two Steps => Total 4. OR 6-2=9-5=9-5 => Total 3 Steps.

6 8 8 => 6-2=8-4=8-4 => Total 3 Steps. OR 6=8-2=8-2 Total 2 Steps. i.e. when the difference is '3' or '4' then we reduce them by '5' which is One Step (better than '2'+'1' OR '2'+'2') .

There is no need to go till min-3 or min-4. Solution passes all test case with just min, min-1, min-2. Makes sense too, logically. Taking min-1 as baseline is helpful for numbers that are min+4 as they can reach min-1 in 1 step (-5). They couldn't reach min or min-2 in 1 one step.

Similarily, Taking min-2 as baseline is helpful for numbers that are min+3 as they can reach min-2 in 1 step (-5). They would have to take 2 steps in reaching min or min-1.

Taking min-3 as baseline is not helpful for any numbers. min+1 number take 2 steps in reaching there. min+2 number takes one step in reaching (-5) but they could have easily reached min in one step too (-2) . min+3 number take 2 steps in reaching min-3 and 2 steps in reaching min again so we don't really need min-3.

You should do two additional per element subtractions by "mini - 1" and "mini - 2" where the smallest element becomes 1 and 2 instead of 0.

Considering the input
1
3
1 5 5
it's not beneficial to transform the array to zero baseline shape 0 4 4 since the algorithm will break the two fours into two 2s resulting in four operations. Correct answer would be three operations.

intcount_operations(vector<int>counts_choc){intmin_elem=*min_element(begin(counts_choc),end(counts_choc));intn_ops0=0;//number of operation assuming base 0intn_ops1=0;//number of operation assuming base 1intn_ops2=0;//number of operation assuming base 2for(intcolleague=0;colleague<counts_choc.size();colleague++){counts_choc[colleague]-=min_elem;//smallest element 0n_ops0+=counts_choc[colleague]/5;n_ops0+=(counts_choc[colleague]%5)/2;n_ops0+=(counts_choc[colleague]%5)%2;counts_choc[colleague]++;//smallest element 1n_ops1+=counts_choc[colleague]/5;n_ops1+=(counts_choc[colleague]%5)/2;n_ops1+=(counts_choc[colleague]%5)%2;counts_choc[colleague]++;//smallest element 2n_ops2+=counts_choc[colleague]/5;n_ops2+=(counts_choc[colleague]%5)/2;n_ops2+=(counts_choc[colleague]%5)%2;}returnmin(n_ops0,min(n_ops1,n_ops2));}intmain(){/* Enter your code here. Read input from STDIN. Print output to STDOUT */intn_tests;cin>>n_tests;vector<vector<int>>data;for(inttest=0;test<n_tests;test++){intn_colleagues;cin>>n_colleagues;vector<int>counts_choc;for(intcolleague=0;colleague<n_colleagues;colleague++){intcount;cin>>count;counts_choc.push_back(count);}data.push_back(counts_choc);}for(inttest=0;test<n_tests;test++){cout<<count_operations(data[test])<<endl;}return0;}

## Equal

You are viewing a single comment's thread. Return to all comments →

Simple Java Implementation -

public static int findutil(int a[],int n,int min) { int count = 0;

Can you please explain your program? It would be of great help.

here, we have to equalize the number of chocolates that each person has. I have categorized the solution into four steps -

1> first thing you have to understand is that giving some chocolates to everyone except one is same as taking away chocolates from one of them. for example - Out of 4 people in a competition,3 gets selected for next round --> 1 person loses. Out of 4 people in a competition, 1 person loses --> 3 gets selected for next round.

2> Using the set of numbers which are given in the question (1,2,5), we can reduce any given value(say 201) to any desired value(say 0,10,37,99....upto 200).So, logically, we would want to reduce the rest of the numbers in the array to the minimum value in it and calculate the number of steps.

3>Now,we require the minimum number of steps, so for every element in array,first we will find the difference between the minimum value in array with the current element and divide it by 5(start with largest number in the set to smallest), then the remainder is divided by 2 and then by 1 and count the number of steps.

2 2 3 7 --> 2 2 2 7 --> 2 2 2 2 (2 steps)

4>But, here comes the tricky part. lets say the input is - 3 6 6. Based on our logic, 3 6 6 --> 3 4 6 --> 3 3 6 --> 3 3 4 --> 3 3 3 (4 steps)

but, there is another minimal way 3 6 6 --> 1 6 6 --> 1 1 6 --> 1 1 1 (3 steps)

So, we will have to check for all the values (min,min-1,min-2,min-3 and min-4) to find out the best possible solution out of all the options.

Hope it helps!

Best possible solution can be found from (min,min-1,min-2). I think we don't need to check for (min-3) and (min-4). I have submitted by calculating optimal from (min,min-1,min-2). Can you provide an example where min-3 or min-4 is more optimal ?

My code :

generally, in dp solution..we start with 1 and build up our solution till n..but i think here (min,min-1,min-2) will do. how did you conclude that we dont require min-3,min-4. Can you elaborate

There is no need to go till min-3 or min-4. Solution passes all test case with just min, min-1, min-2. Makes sense too, logically. Taking min-1 as baseline is helpful for numbers that are min+4 as they can reach min-1 in 1 step (-5). They couldn't reach min or min-2 in 1 one step.

Similarily, Taking min-2 as baseline is helpful for numbers that are min+3 as they can reach min-2 in 1 step (-5). They would have to take 2 steps in reaching min or min-1.

Taking min-3 as baseline is not helpful for any numbers. min+1 number take 2 steps in reaching there. min+2 number takes one step in reaching (-5) but they could have easily reached min in one step too (-2) . min+3 number take 2 steps in reaching min-3 and 2 steps in reaching min again so we don't really need min-3.

Same logic can be applied for min-4 baseline too.

(min,min-1,min-2,min-3andmin-4) this step i didnt understand.why ?ididnt get it.please if you could explain.Yhanks in advance

Hi I have implemented in C++ but getting WA. Any help?

You should do two additional per element subtractions by "mini - 1" and "mini - 2" where the smallest element becomes 1 and 2 instead of 0.

Considering the input 1 3 1 5 5 it's not beneficial to transform the array to zero baseline shape 0 4 4 since the algorithm will break the two fours into two 2s resulting in four operations. Correct answer would be three operations.

1 3 602 437 152 if this case is given than...... what i have to do? i can reduce the no of chocklates by 1,2 or 5