there must be some formula for this because if we increment in each operation then it will take too much time so please help with this
Balife problem greedy
refer to page 11 of this
A[i-1] (if i>0) or A[i+1] (if i < n-1). explain me this condition like this is same in all cases except when i=0 or i=(n-1) so after subtracting 1 from a[i] in which we had to add
A[i-1] (if i>0) or A[i+1] (if i < n-1) is used to avoid runtime error as A[0] and A[n-1] has only one neighbour whereas all other have 2 neighbours
so in which one we should in like to get good results in time and one explained in pdf is very different please explain
we should increase to get god result
to make array all equal, each element should be equal to average (sum_of_all_elements/number_of_elements), now if average is non integer,then no answer exits(eg: 1,2,2 average is 1.66), now if average is integer we don’t have to actually simulate the whole process to get answer!, instead we iterate over the array and look for maximum difference between actual sum and desired sum
Now actual sum is simply addition of all A[i] and desired sum is average*(i+1)
Example : 4, 8, 12, 16
here average is 10 (integer) so answer exists
now iterate from 0 to 3,maxdif=0
i=0, sum=4,disired sum = 10 ,dif = 6,maxdif = 6(take abs value)
i=1, sum=12,disired sum = 20 dif=8, maxdif = 8
i=2, sum=24,disired sum = 30 dif=6 maxdif = 6
i=0, sum=40,disired sum = 40 dif =0 maxdif = 6
hence answer is 8.
why are we multiplying load with(i+1)
and same test case 1 is incorrect wit the code u sent
we multiply with i+1 since we are using 0 based indexing, first element ideally should be average but if we use average*i then this gives 0 for first element. hence we multiply by i+1 instead of i.
bhaiya one test case gone wrong with the code you sent
Download that test case + desired output and see where the code goes wrong