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.
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.
Note:
The boundaries of each input argument are 1 <= left <= right <= 10000.

描述

自分数就是可以整除的数字中每一位数的那个数。 例如，128就是一个自分数，因为128 % 1 == 0, 128 % 2 == 0, and 128 % 8 == 0。 当然，由此判断自分数中不含有数字0。 给定一个下界和上界，输出一个自分数的数组，如果可能的话，包括边界。 注意： 输入的范围1 <= left <= right <= 10000

分析

遍历给定边界的数组，对每个数字进行判断，符合要求的放到要返回的数组。 获取每位上的数字，判断是否能被整除，注意不能为零。

时间复杂度

复杂度为O(mn)，m=right -left，n是for循环里面循环次数

Java

class Solution {  
   public List<Integer> selfDividingNumbers(int left, int right) {
      List<Integer> list = new ArrayList<Integer>();
      for (int num = left;num<=right;num++) {
          if (isSelfDividingNumber(num)) {
             list.add(num);
          }
       }
      return list;
   }
   public boolean isSelfDividingNumber(int num) {
      int n=num;
      while(n>0){
         if (n%10 == 0 || num%(n%10) != 0) {
             return false;
         }
         n/=10;
      }
      return true;
    }
}

C++

class Solution {

public:  
    vector<int> selfDividingNumbers(int left, int right) {
        vector<int> vec ;
        for(int i = left; i <= right ; i++){
            bool flag = true ;
            int t = i ;
            while(t){
                int d = t%10 ;
                if (d == 0 || i%d ){
                    flag = false ;
                    break ;
                }
                t /= 10 ;
            }
            if (flag)
                vec.push_back(i) ;
        }
        return vec ;
    }
};

Swift

class Solution {

     func selfDividingNumbers(_ left: Int, _ right: Int) -> [Int] {
        var arr:[Int] = []
        for i in left...right {
            if isSelfDivingNumber(num: i) {
                arr.append(i)
            }
        }
        return arr
    }

    func isSelfDivingNumber(num:Int) -> Bool {
        var temp = num
        var div = 0
        while temp > 0 {
            div = temp % 10
            if div == 0 {
                return false
            } else if num%div != 0 {
                return false
            } else {
                temp = temp/10
            }
        }
        return true
    }
 }

本题来自LeetCode