leetcode

commit 42556e767047081cafb3e84dc1d673afaca2fca9
parent 0af3b7c97c98d1e13c0170d900cbeb8d97f84ec5
Author: Jack Sangdahl <jack@pngu.org>
Date:   Wed, 25 Jun 2025 19:33:55 -0600

728. self dividing numbers

Diffstat:
A
self_dividing_numbers.c
 | 
53
+++++++++++++++++++++++++++++++++++++++++++++++++++++
A
self_dividing_numbers.py
 | 
30
++++++++++++++++++++++++++++++

2 files changed, 83 insertions(+), 0 deletions(-)
diff --git a/self_dividing_numbers.c b/self_dividing_numbers.c
@@ -0,0 +1,53 @@
+// 728. Self Dividing Numbers
+#include "leetcode.h"
+
+/*
+ * a self-dividing number is a number that is divisible by every digit it
+ * contains. for example, 128 is a self-dividing number because 128 % 1 == 0,
+ * 128 % 2 == 0, and 128 % 8 == 0. a self-dividing number is not allowed to
+ * contain the digit zero. given two integers 'left' and 'right', return a list
+ * of all the self-dividing numbers in the range '[left, right]' (both
+ * inclusive).
+ */
+
+int *selfDividingNumbers(int left, int right, int *returnSize) {
+  int tracker, curr, digit;
+  bool valid;
+  int *ans = (int *)malloc((right - left + 1) * sizeof(int));
+  *returnSize = 0;
+  for (int i = left; i <= right; i++) {
+    curr = i;
+    valid = true;
+    tracker = 0;
+    while (curr > 0) {
+      if (i < 10)
+        break;
+      digit = curr % 10;
+      curr /= 10;
+      if (!digit)
+        valid = false;
+      else if (digit > 1 && !(tracker & (1 << digit))) {
+        valid = !(i % digit);
+        tracker |= (1 << digit);
+      }
+      if (!valid)
+        break;
+    }
+    if (valid)
+      ans[(*returnSize)++] = i;
+  }
+  return ans;
+}
+
+int main() {
+  int rs1, *sdn1 = selfDividingNumbers(1, 22, &rs1);
+  int rs2, *sdn2 = selfDividingNumbers(47, 85, &rs2);
+  for (int i = 0; i < rs1; i++)
+    printf("%d ", sdn1[i]); // expect: [1,2,3,4,5,6,7,8,9,11,12,15,22]
+  printf("\n");
+  for (int i = 0; i < rs1; i++)
+    printf("%d ", sdn2[i]); // expect: [48,55,66,77]
+  printf("\n");
+  free(sdn1);
+  free(sdn2);
+}
diff --git a/self_dividing_numbers.py b/self_dividing_numbers.py
@@ -0,0 +1,30 @@
+# 728. Self Dividing Numbers
+
+"""
+a self-dividing number is a number that is divisible by every digit it
+contains. for example, 128 is a self-dividing number because 128 % 1 == 0,
+128 % 2 == 0, and 128 % 8 == 0. a self-dividing number is not allowed to
+contain the digit zero. given two integers 'left' and 'right', return a list
+of all the self-dividing numbers in the range '[left, right]' (both
+inclusive).
+"""
+
+
+class Solution(object):
+    def selfDividingNumbers(self, left, right):
+        """
+        :type left: int
+        :type right: int
+        :rtype: List[int]
+        """
+        return [
+            i
+            for i in range(left, right + 1)
+            if all((j and (i % j == 0) for j in map(int, str(i))))
+        ]
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.selfDividingNumbers(left=1, right=22))
+    print(obj.selfDividingNumbers(left=47, right=85))