Given N rods of different lengths. The task is to cut all the rods with some maximum integer height ‘h’ such that the sum of cut-off lengths of the rod is maximized and must be greater than M. Print -1 if no such cut is possible.
Note: A rod cannot be cut also.
Examples:
Input: N = 7, M = 8, a[] = {1, 2, 3, 5, 4, 7, 6}
Output: 3
Rod 1 and 2 are untouched, and rod 3, 4, 5, 6, 7 are cut with the cut-off lengths being (3-3) + (4-3) + (5-3) + (7-3) + (6-3) which is equal to 10 which is greater than M = 8.
Input: N = 4, M = 2, a[] = {1, 2, 3, 3}
Output: 2
Approach:
- Sort the array in ascending order
- Run a binary search with values low=0 and high=length[n-1], such that mid=(low+high)/2.
- Run a loop from n-1 till 0 adding the height of the rod cut-off to the sum.
- If the sum is greater than or equal to m, assign low with mid+1 otherwise high will be updated with mid.
- After Binary search is completed the answer will be low-1.
Below is the implementation of the above approach:
C++
// C++ program to find the maximum possible// length of rod which will be cut such that// sum of cut off lengths will be maximum#include <bits/stdc++.h>using namespace std;// Function to run Binary Search to// find maximum cut off lengthint binarySearch(int adj[], int target, int length){ int low = 0; int high = adj[length - 1]; while (low < high) { // f is the flag variable // sum is for the total length cutoff int f = 0, sum = 0; int mid = low + (high - low) / 2; // Loop from higher to lower // for optimization for (int i = length - 1; i >= 0; i--) { // Only if length is greater // than cut-off length if (adj[i] > mid) { sum = sum + adj[i] - mid; } // When total cut off length becomes greater // than desired cut off length if (sum >= target) { f = 1; low = mid + 1; break; } } // If flag variable is not set // Change high if (f == 0) high = mid; } // returning the maximum cut off length return low - 1;}// Driver Functionint main(){ int n1 = 7; int n2 = 8; int adj[] = { 1, 2, 3, 4, 5, 7, 6 }; // Sorting the array in ascending order sort(adj, adj + n1); // Calling the binarySearch Function cout << binarySearch(adj, n2, n1);} |
Java
// Java program to find the // maximum possible length // of rod which will be cut // such that sum of cut off // lengths will be maximumimport java.util.*;class GFG{// Function to run Binary // Search to find maximum // cut off lengthstatic int binarySearch(int adj[], int target, int length){int low = 0;int high = adj[length - 1];while (low < high) { // f is the flag variable // sum is for the total // length cutoff int f = 0, sum = 0; int mid = low + (high - low) / 2; // Loop from higher to lower // for optimization for (int i = length - 1; i >= 0; i--) { // Only if length is greater // than cut-off length if (adj[i] > mid) { sum = sum + adj[i] - mid; } // When total cut off length // becomes greater than // desired cut off length if (sum >= target) { f = 1; low = mid + 1; break; } } // If flag variable is // not set Change high if (f == 0) high = mid;}// returning the maximum // cut off lengthreturn low - 1;}// Driver Codepublic static void main(String args[]){ int n1 = 7; int n2 = 8; int adj[] = { 1, 2, 3, 4, 5, 7, 6 }; // Sorting the array // in ascending order Arrays.sort(adj); // Calling the binarySearch Function System.out.println(binarySearch(adj, n2, n1));}}// This code is contributed// by Arnab Kundu |
Python3
# Python 3 program to find the # maximum possible length of # rod which will be cut such # that sum of cut off lengths # will be maximum# Function to run Binary Search # to find maximum cut off length def binarySearch(adj, target, length) : low = 0 high = adj[length - 1] while (low < high) : # f is the flag variable # sum is for the total # length cutoff # multiple assignments f, sum = 0, 0 # take integer value mid = low + (high - low) // 2; # Loop from higher to lower # for optimization for i in range(length - 1, -1 , -1) : # Only if length is greater # than cut-off length if adj[i] > mid : sum = sum + adj[i] - mid # When total cut off length # becomes greater than # desired cut off length if sum >= target : f = 1 low = mid + 1 break # If flag variable is # not set. Change high if f == 0 : high = mid # returning the maximum # cut off length return low - 1# Driver codeif __name__ == "__main__" : n1 = 7 n2 = 8 # adj = [1,2,3,3] adj = [ 1, 2, 3, 4, 5, 7, 6] # Sorting the array # in ascending order adj.sort() # Calling the binarySearch Function print(binarySearch(adj, n2, n1))# This code is contributed# by ANKITRAI1 |
C#
// C# program to find the // maximum possible length // of rod which will be cut // such that sum of cut off // lengths will be maximumusing System;class GFG{// Function to run Binary // Search to find maximum // cut off lengthstatic int binarySearch(int []adj, int target, int length){int low = 0;int high = adj[length - 1];while (low < high) { // f is the flag variable // sum is for the total // length cutoff int f = 0, sum = 0; int mid = low + (high - low) / 2; // Loop from higher to lower // for optimization for (int i = length - 1; i >= 0; i--) { // Only if length is greater // than cut-off length if (adj[i] > mid) { sum = sum + adj[i] - mid; } // When total cut off length // becomes greater than // desired cut off length if (sum >= target) { f = 1; low = mid + 1; break; } } // If flag variable is // not set Change high if (f == 0) high = mid;}// returning the maximum // cut off lengthreturn low - 1;}// Driver Codepublic static void Main(){ int n1 = 7; int n2 = 8; int []adj = {1, 2, 3, 4, 5, 7, 6}; // Sorting the array // in ascending order Array.Sort(adj); // Calling the binarySearch Function Console.WriteLine(binarySearch(adj, n2, n1));}}// This code is contributed// by Subhadeep Gupta |
PHP
<?php // PHP program to find the maximum // possible length of rod which will // be cut such that sum of cut off // lengths will be maximum// Function to run Binary Search // to find maximum cut off lengthfunction binarySearch(&$adj, $target, $length){ $low = 0; $high = $adj[$length - 1]; while ($low < $high) { // f is the flag variable // sum is for the total // length cutoff $f = 0; $sum = 0; $mid = $low + ($high - $low) / 2; // Loop from higher to lower // for optimization for ($i = $length - 1; $i >= 0; $i--) { // Only if length is greater // than cut-off length if ($adj[$i] > $mid) { $sum = $sum + $adj[$i] - $mid; } // When total cut off length becomes // greater than desired cut off length if ($sum >= $target) { $f = 1; $low = $mid + 1; break; } } // If flag variable is not // set Change high if ($f == 0) $high = $mid; } // returning the maximum cut off length return $low - 1;}// Driver Code$n1 = 7;$n2 = 8;$adj = array( 1, 2, 3, 4, 5, 7, 6 );// Sorting the array in ascending ordersort($adj);// Calling the binarySearch Functionecho (int)binarySearch($adj, $n2, $n1);// This code is contributed by ChitraNayal?> |
Javascript
<script>// Javascript program to find the // maximum possible length // of rod which will be cut // such that sum of cut off // lengths will be maximum// Function to run Binary // Search to find maximum // cut off lengthfunction binarySearch(adj,target,length){let low = 0;let high = adj[length - 1];while (low < high) { // f is the flag variable // sum is for the total // length cutoff let f = 0, sum = 0; let mid = low + Math.floor((high - low) / 2); // Loop from higher to lower // for optimization for (let i = length - 1; i >= 0; i--) { // Only if length is greater // than cut-off length if (adj[i] > mid) { sum = sum + adj[i] - mid; } // When total cut off length // becomes greater than // desired cut off length if (sum >= target) { f = 1; low = mid + 1; break; } } // If flag variable is // not set Change high if (f == 0) high = mid;} // returning the maximum // cut off lengthreturn low - 1;} // Driver Code let n1 = 7;let n2 = 8;let adj=[1, 2, 3, 4, 5, 7, 6 ];// Sorting the array // in ascending orderadj.sort(function(a,b){return a-b;});// Calling the binarySearch Functiondocument.write(binarySearch(adj, n2, n1)); // This code is contributed by avanitrachhadiya2155</script> |
Output:
3
Time Complexity: O(N * log N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
