aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--house_robber4.c36
-rw-r--r--house_robber4.py45
2 files changed, 81 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
+}
diff --git a/house_robber4.py b/house_robber4.py
new file mode 100644
index 0000000..a8fb361
--- /dev/null
+++ b/house_robber4.py
@@ -0,0 +1,45 @@
+# 2560. House Robber IV
+
+"""
+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.
+"""
+
+
+class Solution(object):
+ def minCapability(self, nums, k):
+ """
+ :type nums: List[int]
+ :type k: int
+ :rtype: int
+ """
+ left, right = min(nums), max(nums)
+ while left < right:
+ mid = (left + right) // 2
+ prev, take = 0, False
+ for i in nums:
+ if prev:
+ prev = False
+ continue
+ if i <= mid:
+ take += 1
+ prev = True
+ if take >= k:
+ right = mid
+ else:
+ left = mid + 1
+ return left
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.minCapability(nums=[2, 3, 5, 9], k=2))
+ print(obj.minCapability(nums=[2, 7, 9, 3, 1], k=2))