aboutsummaryrefslogtreecommitdiff
path: root/other/make_sum_divisible_p.cpp
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-03-10 00:36:13 -0600
committerJack Sangdahl <[email protected]>2025-03-10 00:36:13 -0600
commit7c60dee83b436e8e8a667bf9f191beced8de4fc3 (patch)
treeeb7a24ee2067f92245c57bb118e85a1baf15df50 /other/make_sum_divisible_p.cpp
parent5d7cdc215e4ba1ec4cbb24c084cccb5e5e641468 (diff)
downloadleetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.tar.gz
leetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.zip
chore: move cpp and rust code to directory
Diffstat (limited to 'other/make_sum_divisible_p.cpp')
-rw-r--r--other/make_sum_divisible_p.cpp36
1 files changed, 36 insertions, 0 deletions
diff --git a/other/make_sum_divisible_p.cpp b/other/make_sum_divisible_p.cpp
new file mode 100644
index 0000000..993c955
--- /dev/null
+++ b/other/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
+}