aboutsummaryrefslogtreecommitdiff
path: root/house_robber4.c
diff options
context:
space:
mode:
Diffstat (limited to 'house_robber4.c')
-rw-r--r--house_robber4.c36
1 files changed, 36 insertions, 0 deletions
diff --git a/house_robber4.c b/house_robber4.c
new file mode 100644
index 0000000..2e1c6e3
--- /dev/null
+++ b/house_robber4.c
@@ -0,0 +1,36 @@
+// 2560. House Robber IV
+#include "leetcode.h"
+
+/*
+ * there are several consecutive houses along a street, each of which has some
+ * money inside. there is also a robber, who wants to steal money from the
+ * homes, but he refuses to steal from adjacent homes. the capability of the
+ * robber is the maximum amount of money he steals from one house of all the
+ * houses he robbed. you are given an integer array 'nums' representing how much
+ * money is stahsed in each house. more formally, the i'th house from the left
+ * has 'nums[i]' dollars. you are also given an integer 'k', representing the
+ * minimum number of houses the robber will steal from. it is always possible to
+ * steal at least 'k' houses. return the minimum possible capability of the
+ * robber out of all the possible ways to steal at least 'k' houses.
+ */
+
+int minCapability(int *nums, int numsSize, int k) {
+ int left = 1, right = 1e9;
+ while (left < right) {
+ int mid = (left + right) / 2, take = 0;
+ for (int i = 0; i < numsSize; i++)
+ if (nums[i] <= mid)
+ take++, i++;
+ if (take >= k)
+ right = mid;
+ else
+ left = mid + 1;
+ }
+ return left;
+}
+
+int main() {
+ int n1[] = {2, 3, 5, 9}, n2[] = {2, 7, 9, 3, 1};
+ printf("%d\n", minCapability(n1, ARRAY_SIZE(n1), 2)); // expect: 5
+ printf("%d\n", minCapability(n2, ARRAY_SIZE(n2), 2)); // expect: 2
+}