728. Self Dividing Numbers

leetcode hard

#csharp#graph#hard#leetcode#two-pointers

Task

Например, 128 является саморазделяющимся числом, потому что 128 % 1 == 0, 128 % 2 == 0 и 128 % 8 == 0. Саморазделяющееся число не может содержать цифру ноль. Если даны два целых числа left и right, верните список всех саморазделяющихся чисел в диапазоне [left, right].

Пример:

Input: left = 1, right = 22

Output: [1,2,3,4,5,6,7,8,9,11,12,15,22]

C# solution

matched/original

public class Solution {
    public IList<int> SelfDividingNumbers(int left, int right) {
        List<int> result = new List<int>();
        for (int num = left; num <= right; num++) {
            if (IsSelfDividing(num)) {
                result.Add(num);
            }
        }
        return result;
    }
    
    private bool IsSelfDividing(int num) {
        int n = num;
        while (n > 0) {
            int digit = n % 10;
            if (digit == 0 || num % digit != 0) {
                return false;
            }
            n /= 10;
        }
        return true;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public vector<int> SelfDividingNumbers(int left, int right) {
        List<int> result = new List<int>();
        for (int num = left; num <= right; num++) {
            if (IsSelfDividing(num)) {
                result.push_back(num);
            }
        }
        return result;
    }
    
    private bool IsSelfDividing(int num) {
        int n = num;
        while (n > 0) {
            int digit = n % 10;
            if (digit == 0 || num % digit != 0) {
                return false;
            }
            n /= 10;
        }
        return true;
    }
}

Java solution

matched/original

import java.util.ArrayList;
import java.util.List;

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

JavaScript solution

matched/original

var selfDividingNumbers = function(left, right) {
    function isSelfDividing(num) {
        let n = num;
        while (n > 0) {
            let digit = n % 10;
            if (digit === 0 || num % digit !== 0) {
                return false;
            }
            n = Math.floor(n / 10);
        }
        return true;
    }
    
    const result = [];
    for (let num = left; num <= right; num++) {
        if (isSelfDividing(num)) {
            result.push(num);
        }
    }
    return result;
};

Python solution

matched/original

func selfDividingNumbers(_ left: Int, _ right: Int) -> [Int] {
    func isSelfDividing(_ num: Int) -> Bool {
        var n = num
        while n > 0 {
            let digit = n % 10
            if digit == 0 || num % digit != 0 {
                return false
            }
            n /= 10
        }
        return true
    }
    
    var result = [Int]()
    for num in left...right {
        if isSelfDividing(num) {
            result.append(num)
        }
    }
    return result
}

Go solution

matched/original

package main

func selfDividingNumbers(left int, right int) []int {
    var result []int
    for num := left; num <= right; num++ {
        if isSelfDividing(num) {
            result = append(result, num)
        }
    }
    return result
}

func isSelfDividing(num int) bool {
    n := num
    for n > 0 {
        digit := n % 10
        if digit == 0 || num % digit != 0 {
            return false
        }
        n /= 10
    }
    return true
}

Explanation

Algorithm

Переберите все числа в диапазоне от left до right.

Для каждого числа проверьте, является ли оно саморазделяющимся: Разделите число на его цифры. Убедитесь, что ни одна цифра не равна нулю и число делится на каждую из своих цифр без остатка.

Добавьте саморазделяющиеся числа в результативный список и верните его.

😎