Can you please help in it I am not getting proper logic for it

help
, , ,
1

There are
N
students in the classroom, and Rahul is the teacher of the classroom.
Every student has some candies with them. Students start to fight if the difference between the number of candies of any two students is greater than
K
. Rahul’s task is to avoid the fight.
He can choose a pair of students and can increase candy of
1
student by
1
and decrease candy of another student by
1
.
Find the minimum number of operations Rahul has to perform to avoid the fight.

2

My solution might not be optimal.
First find the max and min element of the array and decrease the max by 1 and increase min by 1.
Then again find max and min of this new array and repeat the same until the diff between min and max is less than K.

3

This is by simple brute force but solution can be very much optimised further.
I have just given a starting logic.

4

can you please share more optimied approoch

1 Like
5

I have a way to optimise this logic. Initially we sort out the array and since the maximum and minimum values increase and decrease by at most 1, we can maintain the sorted array easily. I am mentioning here how to maintain the minimum part. Maximum can be maintained in a similar manner.

Consider two possible cases -

  1. a[2]-a[1] > 0 (i.e., the first two elements are different). In this case, increasing the minimum will keep the array sorted and we don’t need to do anything.
  2. a[1]=a[2]=…=a[i]≠a[i+1] - Note that instead of increasing a[1], we can increase a[i] which will also maintain the array as sorted. Such an index i can be found using a modified binary search. Thus each operation can be performed in O(log n).

But this isn’t the best way to approach the question as there can be many operations depending on the constraints for the initial number of candies.

6

have you solved this que?

7

Use the frequency array or map for this quesstion. I have done this using freq array

#include <bits/stdc++.h>
using namespace std;

int main()
{
int n;
int k;
cin>>n>>k;
int ar[n];

for(int i=0;i<n;i++)
{
  cin>>ar[i];
}

sort(ar,ar+n);
int l=ar[n-1]+1;
int freq[l];
for(int i=0;i<l;i++)
freq[i]=0;

for(int i=0;i<n;i++)
{
  freq[ar[i]]++;
}

int  mi=ar[0];
int ma=ar[n-1];
int count=0;

while(abs(ma-mi)>k)
{

freq[mi]--;
freq[mi+1]++;
freq[ma]--;
freq[ma-1]++;

if(freq[mi]==0)
{
  mi=mi+1;
}
if(freq[ma]==0)
{
  ma=ma-1;
}
count++;
}
cout<<count;
return 0;

}