It is simple Binary Search
Sort the array in descending order. Now binary search on the answer. For a particular value check if the array can be divided into subsets with sum not exceeding that particular value.
Can your explian how we can check “the array can be divided into subsets with sum not exceeding that particular value” ??
You are right. i got your idea. but can you explain more on this statement …
" For a particular value check if the array can be divided into subsets with sum not exceeding that particular value. "
thank you for your reply.
Can you provide the link to the problem ? Just to ensure this is not from an ongoing contest !
sure… One of my friend have suggested this question.
Link to Geeksforgeeks courses.
link : Practice | GeeksforGeeks | A computer science portal for geeks
In, Searching course open contest which will contain this question.
link : Practice | GeeksforGeeks | A computer science portal for geeks
here, all courses are for preparation. so, contest is just for practice.
Cool !
You can go through this JAVA code.
Basically what my check function does is to check if I can split the array into number of subsets less or equal to m such that the sum of each subset is <= threshold. So its optimal to choose the value which is just less than threshold value at each step.
Cheers !
You can practice another very similar problem commonly called painters partition problem here
@aman_robotics your logic gives TLE. can you optimize more?
problem link : Practice | GeeksforGeeks | A computer science portal for geeks
Well my complexity for check function is O(NlogN), making the total complexity to be O(Nlog^2N), currently I don’t have any idea how to solve it in O(NlogN) or may be less.
@aman_robotics your logic is wrong, check this case:
1
11
2 2 2 2 2 2 2 2 3 5 12
2
your code gives 19, the correct answer is 18 (5 + 3 + 2 + 2 + 2 + 2 + 2 and 12 + 2 + 2 + 2)
Thanks for pointing it out.
The problem is NP-complete, it cannot be solved in polynomial time. It can be transformed into the bin packing problem. See this explanation:
@aman_robotics your code is going to infinite loop.
Long just_smaller = map.floorKey(curr);
if(just_smaller == null){
cnt++;
curr = threshold;
continue;
}
if just_smaller == null, then value of curr is not change,
you assign again,curr = theshoold,
so just_smaller again make null and its infinite loop.
Hey, there is problem called as :- Allocate Minimum Number of pages/ Painter Partition Problem(that solution got AC) on GFG in your question.
But that’s wrong, as there is a condition (in Allocate Minimum Number of Pages) that partition must be continous, which is not given for your question(I think moderator might forget to mention that)