Size of smallest square that contains N non-overlapping rectangles of given dimensions
Size of smallest square that contains N non-overlapping rectangles of given dimensions Given two positive integers W and H and N rectangles of dimension W*H, the task is to find the smallest size of the square required such that all the N rectangles can be packed without overlapping. Examples:Input: N = 10, W = 2, H = 3Output: 9Explanation:The smallest size of the square is 9 units to pack the given 10 rectangles of size 2*3 as illustrated in the below image: Input: N = 1, W = 3, H = 3Output: 3Approach: The given problem is based on the following observations:It can be shown that one of the optimal spacing of rectangles within a square is given by: The maximum number of rectangles of dimension W*H, that can be fitted in the square with sides X is given by ⌊X/W⌋⋅⌊X/H⌋.The above function is monotonically increasing. Therefore, the idea is to use the Binary Search to find the smallest side of a square that satisfies the given condition.Follow the steps below to solve the problem:Initialize two variables, say low as 1, and high as W*H*N.Iterate until i is less than j and perform the following steps:Find the value of mid as (i + j)/2.Now, if the value (mid/W)*(mid/H) is at most N, then update the value of high as mid.Otherwise, update the value of low as (mid + 1).After completing the above steps, print the value of high as the resultant value.Below is the implementation of the above approach:Python3 def bound(w, h, N, x): val = (x//w)*(x//h) if(val >= N): return True else: return False def FindSquare(N, W, H): i = 1 j = W * H*N while(i < j): mid = i + (j - i)//2 if(bound(W, H, N, mid)): j = mid else: i = mid + 1 return j W = 2H = 3N = 10 print(FindSquare(N, W, H))Time Complexity: O(log(W*H))Auxiliary Space: O(1)Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.