Given an array arr[] consisting of N positive integers representing the lengths of N ropes and a positive integer K, the task is to find the maximum length of the rope that has a frequency of at least K by cutting any ropes in any number of pieces.
Examples:
Input: arr[] = {5, 2, 7, 4, 9}, K = 5
Output: 4
Explanation:
Below are the possible cutting of the ropes:
- arr[0](= 5) is cutted into {4, 1}.
- arr[2](= 7) is cutted into {4, 3}.
- arr[4](= 9) is cutted into {4, 4, 1}.
After the above combinations of cuts, the maximum length is 4, which is of frequency at least(K = 5).
Input: arr[] = {1, 2, 3, 4, 9}, K = 6
Output: 2
Approach: The given problem can be solved by using the Binary Search. Follow the steps below to solve the problem:
- Initialize 3 variables, say low as 1, high as the maximum value of array arr[], and ans as -1, to store the left boundary right boundary for the binary search and to store the maximum possible length of K ropes.
- Iterate until low is less than or equal to high and perform the following steps:
- Find the mid-value of the range [low, high] and store it in a variable say mid.
- Traverse the array arr[] and find the count of ropes of length mid that can be obtained by cutting the ropes and store it in a variable say, count.
- If the value of count is at least K, then update the value of mid as ans and update the value of low as (mid + 1).
- Otherwise, update the value of high as (mid – 1).
- After completing the steps, print the value of ans as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approachÂ
#include <bits/stdc++.h>using namespace std;Â
// Function to find the maximum size// of ropes having frequency at least// K by cutting the given ropesint maximumSize(int a[], int k, int n){    // Stores the left and    // the right boundaries    int low = 1;    int high = *max_element(a, a + n);Â
    // Stores the maximum length    // of rope possible    int ans = -1;Â
    // Iterate while low is less    // than or equal to high    while (low <= high) {Â
        // Stores the mid value of        // the range [low, high]        int mid = low + (high - low) / 2;Â
        // Stores the count of ropes        // of length mid        int count = 0;Â
        // Traverse the array arr[]        for (int c = 0; c < n; c++) {            count += a / mid;        }Â
        // If count is at least K        if (count >= k) {Â
            // Assign mid to ans            ans = mid;Â
            // Update the value            // of low            low = mid + 1;        }Â
        // Otherwise, update the        // value of high        else {            high = mid - 1;        }    }Â
    // Return the value of ans    return ans;}Â
// Driver Codeint main(){Â Â Â Â int arr[] = { 1, 2, 3, 4, 9 };Â Â Â Â int K = 6;Â Â Â Â int n = sizeof(arr) / sizeof(arr[0]);Â Â Â Â cout << (maximumSize(arr, K, n));}Â
// This code is contributed by ukasp |
Java
// Java program for the above approachÂ
import java.util.*;Â
class GFG {Â
    // Function to find the maximum size    // of ropes having frequency at least    // K by cutting the given ropes    static int maximumSize(Integer[] a,                           int k)    {        // Stores the left and        // the right boundaries        int low = 1;        int high = Collections.max(            Arrays.asList(a));Â
        // Stores the maximum length        // of rope possible        int ans = -1;Â
        // Iterate while low is less        // than or equal to high        while (low <= high) {Â
            // Stores the mid value of            // the range [low, high]            int mid = low + (high - low) / 2;Â
            // Stores the count of ropes            // of length mid            int count = 0;Â
            // Traverse the array arr[]            for (int c = 0;                 c < a.length; c++) {                count += a / mid;            }Â
            // If count is at least K            if (count >= k) {Â
                // Assign mid to ans                ans = mid;Â
                // Update the value                // of low                low = mid + 1;            }Â
            // Otherwise, update the            // value of high            else {                high = mid - 1;            }        }Â
        // Return the value of ans        return ans;    }Â
    // Driver Code    public static void main(String[] args)    {        Integer[] arr = { 1, 2, 3, 4, 9 };        int K = 6;        System.out.println(            maximumSize(arr, K));    }} |
Python3
# Python program for the above approachÂ
# Function to find the maximum size# of ropes having frequency at least# K by cutting the given ropesdef maximumSize(a, k):       # Stores the left and    # the right boundaries    low = 1    high = max(a)Â
    # Stores the maximum length    # of rope possible    ans = -1Â
    # Iterate while low is less    # than or equal to high    while (low <= high):Â
        # Stores the mid value of        # the range [low, high]        mid = low + (high - low) // 2Â
        # Stores the count of ropes        # of length mid        count = 0Â
        # Traverse the array arr[]        for c in range(len(a)):            count += a // midÂ
Â
        # If count is at least K        if (count >= k):Â
            # Assign mid to ans            ans = midÂ
            # Update the value            # of low            low = mid + 1Â
        # Otherwise, update the        # value of high        else:            high = mid - 1Â
    # Return the value of ans    return ansÂ
# Driver Codeif __name__ == '__main__':Â Â Â Â arr = [1, 2, 3, 4, 9]Â Â Â Â K = 6Â Â Â Â print(maximumSize(arr, K))Â
# This code is contributed by mohit kumar 29. |
C#
// C# program for the above approachusing System;using System.Linq;Â
class GFG{Â
// Function to find the maximum size// of ropes having frequency at least// K by cutting the given ropesstatic int maximumSize(int[] a, int k){         // Stores the left and    // the right boundaries    int low = 1;    int high = a.Max();Â
    // Stores the maximum length    // of rope possible    int ans = -1;Â
    // Iterate while low is less    // than or equal to high    while (low <= high)    {                 // Stores the mid value of        // the range [low, high]        int mid = low + (high - low) / 2;Â
        // Stores the count of ropes        // of length mid        int count = 0;Â
        // Traverse the array []arr        for(int c = 0;                c < a.Length; c++)         {            count += a / mid;        }Â
        // If count is at least K        if (count >= k)        {                         // Assign mid to ans            ans = mid;Â
            // Update the value            // of low            low = mid + 1;        }Â
        // Otherwise, update the        // value of high        else        {            high = mid - 1;        }    }Â
    // Return the value of ans    return ans;}Â
// Driver Codepublic static void Main(String[] args){Â Â Â Â int[] arr = { 1, 2, 3, 4, 9 };Â Â Â Â int K = 6;Â Â Â Â Â Â Â Â Â Console.WriteLine(Â Â Â Â Â Â Â Â maximumSize(arr, K));}}Â
// This code is contributed by 29AjayKumar |
Javascript
<script>Â Â Â Â Â Â Â Â // Javascript program for the above approachÂ
Â
            // Function to find the maximum size            // of ropes having frequency at least            // K by cutting the given ropes            function maximumSize( a, k) {            // Stores the left and            // the right boundaries            let low = 1;            let high = Math.max.apply(Math, a);                 // Stores the maximum length            // of rope possible            let ans = -1;Â
            // Iterate while low is less            // than or equal to high            while (low <= high) {Â
                // Stores the mid value of                // the range [low, high]                let mid = Math.floor(low + (high - low) / 2);                                 // Stores the count of ropes                // of length mid                let count = 0;Â
                // Traverse the array arr[]                for (let c = 0;                    c < a.length; c++) {                    count += Math.floor(a / mid);                }Â
                // If count is at least K                if (count >= k) {Â
                    // Assign mid to ans                    ans = mid;Â
                    // Update the value                    // of low                    low = mid + 1;                }Â
                // Otherwise, update the                // value of high                else {                    high = mid - 1;                }            }Â
            // Return the value of ans            return ans;        }Â
        // Driver CodeÂ
        let arr = [ 1, 2, 3, 4, 9 ];        let K = 6;        document.write(maximumSize(arr, K))Â
        // This code is contributed by Hritik    </script> |
Output:Â
2
Â
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!
