Java solution with explanation, no toString() conversion


  • 6

    The idea is to traverse each integer sequence from left to right incrementing by one (left, left + 1, left + 2,..., left + n, right). Each time check if the the current number i is self-divided.
    Self-division check is done by using '%' operator(we check each digit of i moving from right to left)
    E.g. if i = 128 number:

    1. 128 % 10 = 8, check 8 != 0;
    2. remove 8 from next step j = 128 / 10 = 12
    3. repeat 1 and 2 until j == 0

    Time complexity is O(nm), where n = right - left, and m is number of digits in iterated number

    class Solution {
        public List<Integer> selfDividingNumbers(int left, int right) {
            List<Integer> list = new ArrayList<>();
            for (int i = left; i <= right; i++) {
                int j = i;
                for (; j > 0; j /= 10) {
                    if ((j % 10 == 0) || (i % (j % 10) != 0)) break;
                }
                if (j == 0) list.add(i); 
            }
            return list;
        }
    }
    

  • 0
    F

    Same idea different expression lol

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

  • 0
    Y

    I think a LinkedList would be more suitable so that you avoid the reallocation of your list if it is full and we still have elements to add. Anyway a small detail!


  • 1

    A minor typo: 128 / 8 == 0 :-)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.