Some test cases give wrong answer. Please explain why and also please let me know the fault in my logic. I’ve basically thought of it like binary search through the maximum possible time it can take( case of 1 painter, hence the sum of lengths of all boards) and minimum time(like 1 painter for each board so that the maximum length board is the minimum time), and then binary search between these two numbers, all the while checking to see if the boards can be managed in the given amount of time
Some test cases give wrong answer
the target value would always be in the searching range.
the searching range will decrease in each loop so that the termination can be reached.
We also know that the values in this range must be in sorted order. Here our target value is the maximum sum of a contiguous section in the optimal allocation of boards. Now how can we apply binary search for this? We can fix the possible low to high range for the target value and narrow down our search to get the optimal allocation.
We can see that the highest possible value in this range is the sum of all the elementsin the array and this happens when we allot 1 painter all the sections of the board. The lowest possible value of this range is the maximum value of the array max, as in this allocation we can allot max to one painter and divide the other sections such that the cost of them is less than or equal to max and as close as possible to max. Now if we consider we use x painters in the above scenarios, it is obvious that as the value in the range increases, the value of x decreases and vice-versa. From this we can find the target value when x=k and use a helper function to find x, the minimum number of painters required when the maximum length of section a painter can paint is give
I have used logic which is very similar to this. Can you once check and please let me know whats wrong with my logic. The maximum and minimum i have set as you explained. The helper function I’m employing is such that to check if a given amount of time is enough for painting or not. I do this first calculating the extra board that I have, that is, boards-painters. After this I calculate how many boards can I club in a contiguous manner and then comparing that with the number of extra boards. Please see the code once. The helper function is check, and the function used to search is named search