Cut Ribbon

Given an array of integers with elements representing lengths of ribbons. Your goal is to obtain k ribbons of equal length cutting the ribbons into as many pieces as you want. Find the maximum integer length L to obtain at least k ribbons of length L.

Example 1:

Input: arr = [1, 2, 3, 4, 9], k = 5
Output: 3
Explanation: cut ribbon of length 9 into 3 pieces of length 3, length 4 into two pieces one of which is length 3 and the other length 1,
and one piece is already is of length 3. So you get 5 total pieces (satisfying k) and the greatest length L possible which would be 3.

First, we will find the largest length of ribbon, as we can’t cut ribbons bigger than their Max piece size.

Second, we will do Binary search to find quickly, the largest cut size of ribbon, to get K equal sizes.

Overall, the time complexity is O(n), we need to find the maximum size of the ribbon.

public static int greatestLength(int[] arr, int k)
{
	//OverallRuntime - O(N), Space - O(1)

        //O(n)
	//We can't cut the ribbon bigger than its Max piece size, so find the max piece size
	int max = int.MinValue;
	for (int i = 0; i < arr.Length; i++)
	{
		max = Math.Max(max, arr[i]);
	}

	//low could be the smallest size - which is 1
	int loSize = 1, hiSize = max;

        //O(LogN)
	//Do binary search to find the the optimum size faster, than lierar search
	while (loSize <= hiSize)
	{
		int midSize = loSize + (hiSize - loSize) / 2;
		int countPieceByMidSize = getLen(arr, midSize);

		// countPieceByMidSize > = k, we can further go for bigger 'size' cut, to see if we still atleast k cuts
		if (countPieceByMidSize >= k)
		{
			loSize = midSize + 1;
		}
		else
		{
			hiSize = midSize - 1;
		}
	}

	//return the max size
	return hiSize;
}

private static int getLen(int[] arr, int target)
{
        //O(n)
	int res = 0;
	for (int i = 0; i < arr.Length; i++)
	{
		//add the count, by splitting a[i] by target
		res += (arr[i] / target);
	}
	return res;
}
<script type="text/javascript" src="https://platform.linkedin.com/badges/js/profile.js" async defer></script>

Leave a Reply

Your email address will not be published. Required fields are marked *