diff options
-rw-r--r-- | find_integer_add_arr2.c | 48 | ||||
-rw-r--r-- | find_integer_add_arr2.py | 44 |
2 files changed, 92 insertions, 0 deletions
diff --git a/find_integer_add_arr2.c b/find_integer_add_arr2.c new file mode 100644 index 0000000..f9edc51 --- /dev/null +++ b/find_integer_add_arr2.c @@ -0,0 +1,48 @@ +// 3132. Find the Integer Added to Array II +#include "leetcode.h" + +/* + * you are given two integer arrays 'nums1' and 'nums2'. from 'nums1', two + * elements have been removed, and all other elements have been increased or + * decreased in the case of negative by an integer, represented by the variable + * 'x'. as a result, 'nums1' becomes equal to 'nums2'. two arrays are considered + * equal when they contain the same integers with the same frequencies. return + * the minimum possible integer 'x' that achieves this equivalence. + */ + +int cmp(const void *a, const void *b) { return *((int *)a) - *((int *)b); } + +int minimumAddedInteger(int *nums1, int nums1Size, int *nums2, int nums2Size) { + int diff, min = INT_MAX; + qsort(nums1, nums1Size, sizeof(int), cmp); + qsort(nums2, nums2Size, sizeof(int), cmp); + for (int i = 0; i < nums1Size; i++) + for (int j = i + 1; j < nums1Size; j++) { + if (!i) + diff = (j == 1) ? nums2[0] - nums1[2] : nums2[0] - nums1[1]; + else + diff = nums2[0] - nums1[0]; + bool match = true; + for (int k = 0, l = 0; k < nums2Size; l++) { + if (l == i || l == j) + continue; + else if (nums1[l] + diff != nums2[k]) { + match = false; + break; + } + k++; + } + if (match && diff < min) + min = diff; + } + return min; +} + +int main() { + int n11[] = {4, 20, 16, 12, 8}, n21[] = {14, 18, 10}, n12[] = {3, 5, 5, 3}, + n22[] = {7, 7}; + printf("%d\n", minimumAddedInteger(n11, ARRAY_SIZE(n11), n21, + ARRAY_SIZE(n21))); // expect: -2 + printf("%d\n", minimumAddedInteger(n12, ARRAY_SIZE(n12), n22, + ARRAY_SIZE(n22))); // expect: 2 +} diff --git a/find_integer_add_arr2.py b/find_integer_add_arr2.py new file mode 100644 index 0000000..b920d90 --- /dev/null +++ b/find_integer_add_arr2.py @@ -0,0 +1,44 @@ +# 3132. Find the Integer Added to Array II + +""" +you are given two integer arrays 'nums1' and 'nums2'. from 'nums1', two +elements have been removed, and all other elements have been increased or +decreased in the case of negative by an integer, represented by the variable +'x'. as a result, 'nums1' becomes equal to 'nums2'. two arrays are considered +equal when they contain the same integers with the same frequencies. return +the minimum possible integer 'x' that achieves this equivalence. +""" + + +class Solution(object): + def minimumAddedInteger(self, nums1, nums2): + """ + :type nums1: List[int] + :type nums2: List[int] + :rtype: int + """ + m, ans = len(nums1), float("-inf") + nums1.sort() + nums2.sort() + + def check(diff): + idx = 0 + for n2 in nums2: + n1 = n2 + diff + while idx < m and nums1[idx] != n1: + idx += 1 + if idx >= m: + return False + idx += 1 + return True + + for diff in [nums1[0] - nums2[0], nums1[1] - nums2[0], nums1[2] - nums2[0]]: + if check(diff): + ans = max(ans, diff) + return -ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.minimumAddedInteger(nums1=[4, 20, 16, 12, 8], nums2=[14, 18, 10])) + print(obj.minimumAddedInteger(nums1=[3, 5, 5, 3], nums2=[7, 7])) |