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.
Also, a self-dividing number is not allowed to contain the digit zero.
Given a lower and upper number bound, output a list of every possible self dividing number, including the bounds if possible.
Example 1:
Input:
left = 1, right = 22
Output: 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22
bool isDividingNumbers(int num)
{
int tmp = num;
int dig = 0;
while(tmp)
{
dig = tmp % 10;
if(0 == dig || num % dig)
return false;
tmp /= 10;
}
return true;
}
/**
* Return an array of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/
int* selfDividingNumbers(int left, int right, int* returnSize)
{
*returnSize = 0;
int k = 0;
for(int i = left;i <= right;i++)
{
if(isDividingNumbers(i))
(*returnSize)++;
}
int *res = (int *)malloc(*returnSize * sizeof(int));
for(int i = left;i <= right;i++)
{
if(isDividingNumbers(i))
res[k++] = i;
}
return res;
}
bool isDividingNumbers(int num)
{
int tmp = num;
int dig = 0;
while(tmp)
{
dig = tmp % 10;
if(0 == dig || num % dig)
return false;
tmp /= 10;
}
return true;
}
/**
* Return an array of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/
int* selfDividingNumbers(int left, int right, int* returnSize)
{
*returnSize = 0;
int size = 32;
/*malloc 32 int at begin*/
int *res = (int *)malloc( size * sizeof(int));
for(int i = left;i <= right;i++)
{
if(isDividingNumbers(i))
{
if((*returnSize + 1) % 31==0)
{
size += 32;
res = (int *)realloc(res,sizeof(int)*size);
}
res[(*returnSize)++] = i;
}
}
return res;
}
第二种方法使用了realloc函数,两种方法在leetcode上的执行时间均为4ms.