diff options
author | Jack Sangdahl <[email protected]> | 2025-03-05 19:26:24 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-03-05 19:26:24 -0700 |
commit | 38751b396e4922973ee2db29ff9eb2a22793c0bb (patch) | |
tree | 1d3ae44218e4e22b45b5333b092410ee52dba4b0 | |
parent | 63f2810c6d4c7081be8ac26b6a70f9323b4ddcd1 (diff) | |
download | leetcode-38751b396e4922973ee2db29ff9eb2a22793c0bb.tar.gz leetcode-38751b396e4922973ee2db29ff9eb2a22793c0bb.zip |
2965. find missing and repeated values
-rw-r--r-- | find_missing_repeated_val.c | 55 | ||||
-rw-r--r-- | find_missing_repeated_val.py | 35 |
2 files changed, 90 insertions, 0 deletions
diff --git a/find_missing_repeated_val.c b/find_missing_repeated_val.c new file mode 100644 index 0000000..0514a74 --- /dev/null +++ b/find_missing_repeated_val.c @@ -0,0 +1,55 @@ +// 2965. Find Missing and Repeated Values +#include "leetcode.h" + +/* + * you are given a 0-indexed 2d integer matrix 'grid' of size 'n * n' with + * values in the range '[1, n^2]'. each integer appears exactly once except 'a' + * which appears twice and 'b' which is missing. the task is to find the + * repeating and missing numbers 'a' and 'b'. return a 0-indexed integer array + * 'ans' of size '2' where 'ans[0]' equals to 'a' and 'ans[1]' equals 'b'. + */ + +int *findMissingAndRepeatedValues(int **grid, int gridSize, int *gridColSize, + int *returnSize) { + int n = gridSize, repeated = 0, missing = 0; + int *cnt = (int *)calloc((n * n + 1), sizeof(int)); + for (int i = 0; i < n; ++i) + for (int j = 0; j < gridColSize[i]; ++j) { + int num = grid[i][j]; + cnt[num]++; + if (cnt[num] == 2) + repeated = num; + } + for (int i = 1; i <= n * n; ++i) + if (!cnt[i]) { + missing = i; + break; + } + int *ans = (int *)malloc(2 * sizeof(int)); + ans[0] = repeated; + ans[1] = missing; + *returnSize = 2; + return ans; +} + +int main() { + int g1i[2][2] = {{1, 3}, {2, 2}}, + g2i[3][3] = {{9, 1, 7}, {8, 9, 2}, {3, 4, 6}}; + struct two_d_arr g1, g2; + two_d_arr_init(&g1, ARRAY_SIZE(g1i), ARRAY_SIZE(g1i[0]), g1i); + two_d_arr_init(&g2, ARRAY_SIZE(g2i), ARRAY_SIZE(g2i[0]), g2i); + int rs1, *fmarv1 = findMissingAndRepeatedValues(g1.arr, g1.row_size, + g1.col_size, &rs1); + int rs2, *fmarv2 = findMissingAndRepeatedValues(g2.arr, g2.row_size, + g2.col_size, &rs2); + for (int i = 0; i < rs1; i++) + printf("%d ", fmarv1[i]); // expect: 2 4 + printf("\n"); + for (int i = 0; i < rs2; i++) + printf("%d ", fmarv2[i]); // expect: 9 5 + printf("\n"); + free(fmarv1); + free(fmarv2); + two_d_arr_free(&g1); + two_d_arr_free(&g2); +} diff --git a/find_missing_repeated_val.py b/find_missing_repeated_val.py new file mode 100644 index 0000000..d8a90ae --- /dev/null +++ b/find_missing_repeated_val.py @@ -0,0 +1,35 @@ +# 2965. Find Missing and Repeated Values + +""" +you are given a 0-indexed 2d integer matrix 'grid' of size 'n n' with +values in the range '[1, n^2]'. each integer appears exactly once except 'a' +which appears twice and 'b' which is missing. the task is to find the +repeating and missing numbers 'a' and 'b'. return a 0-indexed integer array +'ans' of size '2' where 'ans[0]' equals to 'a' and 'ans[1]' equals 'b'. +""" + + +class Solution(object): + def findMissingAndRepeatedValues(self, grid): + """ + :type grid: List[List[int]] + :rtype: List[int] + """ + repeated, missing, n = 0, 0, len(grid) + cnt = [0] * (n * n + 1) + for i in grid: + for j in i: + cnt[j] += 1 + if cnt[j] == 2: + repeated = j + for i in range(1, n * n + 1): + if cnt[i] == 0: + missing = i + break + return [repeated, missing] + + +if __name__ == "__main__": + obj = Solution() + print(obj.findMissingAndRepeatedValues(grid=[[1, 3], [2, 2]])) + print(obj.findMissingAndRepeatedValues(grid=[[9, 1, 7], [8, 9, 2], [3, 4, 6]])) |