add 1891

fishercoder1534 · fishercoder1534 · commit ffbd96a5420f · 2022-01-27T08:47:27.000-08:00
diff --git a/README.md b/README.md
@@ -112,6 +112,7 @@ _If you like this project, please leave me a star._ &#9733;
 |1903|[Largest Odd Number in String](https://leetcode.com/problems/largest-odd-number-in-string/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1903.java) |[:tv:](https://youtu.be/IIt_ARZzclY)|Easy|Greedy|
 |1897|[Redistribute Characters to Make All Strings Equal](https://leetcode.com/problems/redistribute-characters-to-make-all-strings-equal/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1897.java) ||Easy|String, Greedy|
 |1893|[Check if All the Integers in a Range Are Covered](https://leetcode.com/problems/check-if-all-the-integers-in-a-range-are-covered/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1893.java) ||Easy|Array, HashTable, Prefix Sum|
+|1891|[Cutting Ribbons](https://leetcode.com/problems/cutting-ribbons/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1891.java) ||Medium|Array, Binary Search|
 |1886|[Determine Whether Matrix Can Be Obtained By Rotation](https://leetcode.com/problems/determine-whether-matrix-can-be-obtained-by-rotation/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1886.java) ||Easy|Array|
 |1880|[Check if Word Equals Summation of Two Words](https://leetcode.com/problems/check-if-word-equals-summation-of-two-words/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1880.java) ||Easy|String|
 |1877|[Minimize Maximum Pair Sum in Array](https://leetcode.com/problems/minimize-maximum-pair-sum-in-array/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1877.java) ||Medium|Greedy, Sort|
diff --git a/src/main/java/com/fishercoder/solutions/_1891.java b/src/main/java/com/fishercoder/solutions/_1891.java
@@ -0,0 +1,54 @@
+package com.fishercoder.solutions;
+
+import java.util.Arrays;
+
+public class _1891 {
+    public static class Solution1 {
+        /**
+         * My completely original solution on 1/27/2022.
+         */
+        public int maxLength(int[] ribbons, int k) {
+            long sum = 0l;
+            int max = ribbons[0];
+            for (int num : ribbons) {
+                sum += num;
+                max = Math.max(max, num);
+            }
+            if (sum < k) {
+                return 0;
+            } else if (sum == k) {
+                return 1;
+            } else {
+                Arrays.sort(ribbons);
+                int left = 1;
+                int right = max;
+                int ans = 1;
+                while (left < right) {
+                    int mid = left + (right - left) / 2;
+                    int count = 0;
+                    for (int i = ribbons.length - 1; i >= 0; i--) {
+                        count += ribbons[i] / mid;
+                        if (count >= k) {
+                            ans = Math.max(ans, mid);
+                            break;
+                        }
+                    }
+                    if (count < k) {
+                        right = mid - 1;
+                    } else {
+                        left = mid + 1;
+                    }
+                }
+                int count = 0;
+                for (int i = ribbons.length - 1; i >= 0; i--) {
+                    count += ribbons[i] / left;
+                    if (count >= k) {
+                        ans = Math.max(ans, left);
+                        return ans;
+                    }
+                }
+                return ans;
+            }
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_1891Test.java b/src/test/java/com/fishercoder/_1891Test.java
@@ -0,0 +1,53 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._1891;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class _1891Test {
+    private static _1891.Solution1 solution1;
+    private static int[] ribbons;
+    private static int k;
+    private static int expected;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _1891.Solution1();
+    }
+
+    @Test
+    public void test1() {
+        ribbons = new int[]{9, 7, 5};
+        k = 3;
+        expected = 5;
+        assertEquals(expected, solution1.maxLength(ribbons, k));
+    }
+
+    @Test
+    public void test2() {
+        ribbons = new int[]{7, 5, 9};
+        k = 4;
+        expected = 4;
+        assertEquals(expected, solution1.maxLength(ribbons, k));
+    }
+
+    @Test
+    public void test3() {
+        ribbons = new int[]{5, 7, 9};
+        k = 22;
+        expected = 0;
+        assertEquals(expected, solution1.maxLength(ribbons, k));
+    }
+
+    @Test
+    public void test4() {
+        ribbons = new int[]{100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 1, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000};
+        k = 49;
+        expected = 100000;
+        assertEquals(expected, solution1.maxLength(ribbons, k));
+    }
+
+
+}
