leetcode

commit b05b821f2432ed8d1a770a9c96abf9726c3d30fe
parent 131583580a2ae17e7e5b17cfa3f41f0ea6645f43
Author: Jack Sangdahl <jack@pngu.org>
Date:   Thu, 30 Oct 2025 22:13:52 -0600

3289. the two sneaky numbers of digitville

Diffstat:
A
two_sneaky_nums.c
 | 
48
++++++++++++++++++++++++++++++++++++++++++++++++
A
two_sneaky_nums.py
 | 
43
+++++++++++++++++++++++++++++++++++++++++++

2 files changed, 91 insertions(+), 0 deletions(-)
diff --git a/two_sneaky_nums.c b/two_sneaky_nums.c
@@ -0,0 +1,48 @@
+// 3289. The Two Sneaky Numbers of Digitville
+#include "leetcode.h"
+
+/*
+ * in the town of digitville, there was a list of numbers called 'nums'
+ * containing integers from 0 to 'n - 1'. each number was supposed to appear
+ * exactly once in the list, however two mischevious numbers snuck in an
+ * additional time, making the list longer than usual. as the town detective,
+ * your task is to find these two sneaky numbers. return an array of size 2
+ * containing the two numbers, so peace can return to digitville.
+ */
+
+int *getSneakyNumbers(int *nums, int numsSize, int *returnSize) {
+  int *ans = (int *)malloc(2 * sizeof(int)), n = numsSize - 2;
+  *returnSize = 2;
+  unsigned int x = nums[n] ^ nums[n + 1];
+  for (int i = 0; i < n; i++)
+    x ^= i ^ nums[i];
+  int y = 31 - __builtin_clz(x);
+  for (int i = 0; i < n; i++) {
+    ans[(i >> y) & 1] ^= i;
+    ans[(nums[i] >> y) & 1] ^= nums[i];
+  }
+  ans[(nums[n] >> y) & 1] ^= nums[n];
+  ans[(nums[n + 1] >> y) & 1] ^= nums[n + 1];
+  return ans;
+}
+
+int main() {
+  int n1[] = {0, 1, 1, 0}, rs1;
+  int n2[] = {0, 3, 2, 1, 3, 2}, rs2;
+  int n3[] = {7, 1, 5, 4, 3, 4, 6, 0, 9, 5, 8, 2}, rs3;
+  int *gsn1 = getSneakyNumbers(n1, ARRAY_SIZE(n1), &rs1);
+  int *gsn2 = getSneakyNumbers(n2, ARRAY_SIZE(n2), &rs2);
+  int *gsn3 = getSneakyNumbers(n3, ARRAY_SIZE(n3), &rs3);
+  for (int i = 0; i < rs1; i++)
+    printf("%d ", gsn1[i]); // expect: 0 1
+  printf("\n");
+  for (int i = 0; i < rs2; i++)
+    printf("%d ", gsn2[i]); // expect: 2 3
+  printf("\n");
+  for (int i = 0; i < rs3; i++)
+    printf("%d ", gsn3[i]); // expect: 4 5
+  printf("\n");
+  free(gsn1);
+  free(gsn2);
+  free(gsn3);
+}
diff --git a/two_sneaky_nums.py b/two_sneaky_nums.py
@@ -0,0 +1,43 @@
+# 3289. The Two Sneaky Numbers of Digitville
+
+"""
+in the town of digitville, there was a list of numbers called 'nums'
+containing integers from 0 to 'n - 1'. each number was supposed to appear
+exactly once in the list, however two mischevious numbers snuck in an
+additional time, making the list longer than usual. as the town detective,
+your task is to find these two sneaky numbers. return an array of size 2
+containing the two numbers, so peace can return to digitville.
+"""
+
+
+class Solution(object):
+    def getSneakyNumbers(self, nums):
+        """
+        :type nums: List[int]
+        :rtype: List[int]
+        """
+        n, x = len(nums) - 2, 0
+        for i in nums:
+            x ^= i
+        for i in range(n):
+            x ^= i
+        diff = x & -x
+        a, b = 0, 0
+        for i in nums:
+            if i & diff == 0:
+                a ^= i
+            else:
+                b ^= i
+        for i in range(n):
+            if i & diff == 0:
+                a ^= i
+            else:
+                b ^= i
+        return [a, b]
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.getSneakyNumbers(nums=[0, 1, 1, 0]))
+    print(obj.getSneakyNumbers(nums=[0, 3, 2, 1, 3, 2]))
+    print(obj.getSneakyNumbers(nums=[7, 1, 5, 4, 3, 4, 6, 0, 9, 5, 8, 2]))