diff options
author | Jack Sangdahl <[email protected]> | 2025-06-25 19:33:55 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-06-25 19:33:55 -0600 |
commit | 42556e767047081cafb3e84dc1d673afaca2fca9 (patch) | |
tree | 3f90bff7c7e52cb54addc70af3a6bddc26031c61 | |
parent | 0af3b7c97c98d1e13c0170d900cbeb8d97f84ec5 (diff) | |
download | leetcode-42556e767047081cafb3e84dc1d673afaca2fca9.tar.gz leetcode-42556e767047081cafb3e84dc1d673afaca2fca9.zip |
728. self dividing numbers
-rw-r--r-- | self_dividing_numbers.c | 53 | ||||
-rw-r--r-- | self_dividing_numbers.py | 30 |
2 files changed, 83 insertions, 0 deletions
diff --git a/self_dividing_numbers.c b/self_dividing_numbers.c new file mode 100644 index 0000000..d0d19b6 --- /dev/null +++ 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 new file mode 100644 index 0000000..66d8735 --- /dev/null +++ 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)) |