aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--smallest_missing_non_neg_int.c30
-rw-r--r--smallest_missing_non_neg_int.py33
2 files changed, 63 insertions, 0 deletions
diff --git a/smallest_missing_non_neg_int.c b/smallest_missing_non_neg_int.c
new file mode 100644
index 0000000..94e0271
--- /dev/null
+++ b/smallest_missing_non_neg_int.c
@@ -0,0 +1,30 @@
+// 2598. Smallest Missing Non-negative Integer After Operations
+#include "leetcode.h"
+
+/*
+ * you are given a 0-indexed integer array 'nums' and an integer 'value'. in one
+ * operation, you can add or subtract 'value' from any element of 'nums'. the
+ * mex (minimum excluded) of an array is the smallest non-negative integer in
+ * it. return the mex of 'nums' after applying the mentioned operation any
+ * number of times.
+ */
+
+int findSmallestInteger(int *nums, int numsSize, int value) {
+ long long x, ans = 0;
+ int *rem = (int *)calloc(value, sizeof(int));
+ for (int i = 0; i < numsSize; i++) {
+ x = ((nums[i] % value) + value) % value;
+ rem[x]++;
+ }
+ while (rem[ans % value]--)
+ ans++;
+ free(rem);
+ return ans;
+}
+
+int main() {
+ int n1[] = {1, -10, 7, 13, 6, 8};
+ int n2[] = {1, -10, 7, 13, 6, 8};
+ printf("%d\n", findSmallestInteger(n1, ARRAY_SIZE(n1), 5)); // expect: 4
+ printf("%d\n", findSmallestInteger(n2, ARRAY_SIZE(n2), 7)); // expect: 2
+}
diff --git a/smallest_missing_non_neg_int.py b/smallest_missing_non_neg_int.py
new file mode 100644
index 0000000..265237e
--- /dev/null
+++ b/smallest_missing_non_neg_int.py
@@ -0,0 +1,33 @@
+# 2598. Smallest Missing Non-negative Integer After Operations
+
+"""
+you are given a 0-indexed integer array 'nums' and an integer 'value'. in one
+operation, you can add or subtract 'value' from any element of 'nums'. the
+mex (minimum excluded) of an array is the smallest non-negative integer in
+it. return the mex of 'nums' after applying the mentioned operation any
+number of times.
+"""
+
+
+class Solution(object):
+ def findSmallestInteger(self, nums, value):
+ """
+ :type nums: List[int]
+ :type value: int
+ :rtype: int
+ """
+ rem = [0] * value
+ for x in nums:
+ curr = (x % value + value) % value
+ rem[curr] += 1
+ ans = 0
+ while rem[ans % value]:
+ rem[ans % value] -= 1
+ ans += 1
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.findSmallestInteger(nums=[1, -10, 7, 13, 6, 8], value=5))
+ print(obj.findSmallestInteger(nums=[1, -10, 7, 13, 6, 8], value=7))