Maximum length possible by cutting N given woods into at least K pieces | C ++ program to implement the above approach ; Function to check if it is possible to cut woods into K pieces of length len ; Stores count of pieces having length equal to K ; Traverse wood [ ] array ; Update count ; Function to find the maximum value of L ; Stores minimum possible of L ; Stores maximum possible value of L ; Apply binary search over the range [ left , right ] ; Stores mid value of left and right ; If it is possible to cut woods into K pieces having length of each piece equal to mid ; Update left ; Update right ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool isValid ( int wood [ ] , int N , int len , int K ) { int count = 0 ; for ( int i = 0 ; i < N ; i ++ ) { count += wood [ i ] / len ; } return count >= K ; } int findMaxLen ( int wood [ ] , int N , int K ) { int left = 1 ; int right = * max_element ( wood , wood + N ) ; while ( left <= right ) { int mid = left + ( right - left ) / 2 ; if ( isValid ( wood , N , mid , K ) ) { left = mid + 1 ; } else { right = mid - 1 ; } } return right ; } int main ( ) { int wood [ ] = { 5 , 9 , 7 } ; int N = sizeof ( wood ) / sizeof ( wood [ 0 ] ) ; int K = 4 ; cout << findMaxLen ( wood , N , K ) ; }