https://ide.codingblocks.com/s/347570 - one test case is failing
Balife - Greedy question
Hey @tusharjha9835
Did 2 changes in ur code and mentioned them in comments
Approach:
base case : if number of jobs of all processors is not divisible by n print -1.
else
find average.
lets say a[i] is the list of jobs assigned to i th processor.
- from each job a[i] do a[i] - avg. if a[i] is +ve it means it has to export this many jobs to neighbors and -ve means it has to import this may jobs from neighbors .
- for all i do a[i] =a[i] + a[i - 1] i.e. find sum till i.
- find max absolute value from a[i] and print it.
explanation:
lets say a[i] after performing step 1 is: [ 2 ,-5, 7, -4]
after performing step 2 array will become [2, -3, 4, 0]
what it means is that first processor has 2 extra jobs and it can export it in 2 round.
2nd processor has 5 jobs to import. It can take 2 from 1st processor, it has still 3 more to import. and it can be done in 3 rounds.
3rd processor has 7 jobs to export. It can export 3 to previous processor in 3 round and it has remaining 4 jobs, which can be exported in 4 rounds to the next processor.
4th processor has to import 4 jobs and it can import it from previous processor in 4 rounds. Hence max rounds is the max absolute value from a[i].
Do hit the like button and mark this as resolved