aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-10-02 21:35:07 -0600
committerJack Sangdahl <[email protected]>2024-10-02 21:35:07 -0600
commit82fb310c19c94b81f495458d5e653e9338d22858 (patch)
tree80f6c679ee9631a23a1555281abf5684ec96225b
parent2c57d963fbbef6543d90a1ee08b13b5eee0813b0 (diff)
downloadleetcode-82fb310c19c94b81f495458d5e653e9338d22858.tar.gz
leetcode-82fb310c19c94b81f495458d5e653e9338d22858.zip
1590. make sum divisible by p
-rw-r--r--make_sum_divisible_p.cpp36
-rw-r--r--make_sum_divisible_p.py34
2 files changed, 70 insertions, 0 deletions
diff --git a/make_sum_divisible_p.cpp b/make_sum_divisible_p.cpp
new file mode 100644
index 0000000..993c955
--- /dev/null
+++ b/make_sum_divisible_p.cpp
@@ -0,0 +1,36 @@
+// 1590. Make Sum Divisible by P
+#include "leetcode.h"
+
+/*
+ * given an array of positive integers 'nums', remove the smallest subarray
+ * (possibly empty) such that the sum of the remaining elements is divisible by
+ * 'p'. it is not allowed to remove the whole array. return the length of the
+ * smallest subarray that you need to remove, or -1 if it is impossible. a
+ * subarray is defined as a contiguous block of elements in the array.
+ */
+
+class Solution {
+public:
+ int minSubarray(vector<int> &nums, int p) {
+ int n = nums.size(), ans = n, req = 0, curr = 0;
+ for (auto i : nums)
+ req = (req + i) % p;
+ unordered_map<int, int> dp = {{0, -1}};
+ for (int i = 0; i < n; i++) {
+ curr = (curr + nums[i]) % p;
+ dp[curr] = i;
+ int need = (curr - req + p) % p;
+ if (dp.count(need))
+ ans = min(ans, i - dp[need]);
+ }
+ return ans < n ? ans : -1;
+ }
+};
+
+int main() {
+ Solution obj;
+ vector<int> n1 = {3, 1, 4, 2}, n2 = {6, 3, 5, 2}, n3 = {1, 2, 3};
+ printf("%d\n", obj.minSubarray(n1, 6)); // expect: 1
+ printf("%d\n", obj.minSubarray(n2, 9)); // expect: 2
+ printf("%d\n", obj.minSubarray(n3, 3)); // expect: 0
+}
diff --git a/make_sum_divisible_p.py b/make_sum_divisible_p.py
new file mode 100644
index 0000000..7efe282
--- /dev/null
+++ b/make_sum_divisible_p.py
@@ -0,0 +1,34 @@
+# 1590. Make Sum Divisible by P
+
+"""
+given an array of positive integers 'nums', remove the smallest subarray
+(possibly empty) such that the sum of the remaining elements is divisible by
+'p'. it is not allowed to remove the whole array. return the length of the
+smallest subarray that you need to remove, or -1 if it is impossible. a
+subarray is defined as a contiguous block of elements in the array.
+"""
+
+
+class Solution(object):
+ def minSubarray(self, nums, p):
+ """
+ :type nums: List[int]
+ :type p: int
+ :rtype: int
+ """
+ req = sum(nums) % p
+ dp, curr = {0: -1}, 0
+ ans = n = len(nums)
+ for i, j in enumerate(nums):
+ curr = (curr + j) % p
+ dp[curr] = i
+ if (curr - req) % p in dp:
+ ans = min(ans, i - dp[(curr - req) % p])
+ return ans if ans < n else -1
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.minSubarray(nums=[3, 1, 4, 2], p=6))
+ print(obj.minSubarray(nums=[6, 3, 5, 2], p=9))
+ print(obj.minSubarray(nums=[1, 2, 3], p=3))