Binary Search in forest | Must do coding questions for Product Based Companies
Binary Search in forest | Must do coding questions for Product Based Companies
Binary Search in forest
Subscribe to my channel --- / @codersbyyutish3249
Link to Ultimate Leetcode Challenge Playlist --- • Ultimate Leetcode Challenge
Also checkout my playlist on Coding Interview Problems --- • Coding Interview Problems for Beginners
-------------------------------------------------------------------------------------------------------------------
Problem Statement - There are n trees in a forest. The heights of the trees is stored in array tree[], where tree[i] denotes the height of the ith tree in the forest. If the ith tree is cut at a height H, then the wood collected is tree[i] - H, provided tree[i] greater than H. If the total woods that needs to be collected is exactly equal to k, find the height H at which every tree should be cut (all trees have to be cut at the same height). If it is not possible then return -1 else return H.
Example 1:
Input:
n = 5, k = 4
nums[] = {2, 3, 6, 2, 4}
Output: 3
Explanation: Wood collected by cutting trees
at height 3 = 0 + 0 + (6-3) + 0 + (4-3) = 4
hence 3 is to be subtracted from all numbers.
Since 2 is lesser than 3, nothing gets
subtracted from it.
Example 2:
Input:
n = 6, k = 8
nums[] = {1, 7, 6, 3, 4, 7}
Output: 4
Explanation: Wood collected by cutting trees
at height 4 = 0+(7-4)+(6-4)+0+0+(7-4) = 8
Your Task:
Your task is to complete the function find_height(). This function takes the array tree[ ], and the integers n and k as input parameters and returns the height at which trees have to be cut. If no positive integer value of height is possible, return -1.
Expected Time Complexity: O(n log h)
Expected Auxiliary Space: O(1)
Constraints:
n = [1, 104]
tree[i] = [1, 103]
k = [1, 104]
Link to problem: https://practice.geeksforgeeks.org/pr...
#shorts #timeenthusiast #geeksforgeeks