Solving Popular Algorithms: Self Dividing Numbers
Welcome back to another week of tackling algorithms. Today, we are going to be looking at a leetcode problem called Self Dividing Numbers. This problem, while not too difficult, did require a bit more creative thinking and I think it will be a great problem to give a go if you are just starting out solving algorithms.
The Problem
You might be wondering what a “self dividing number” is. Basically, a self dividing number is a number who can be evenly divided (aka with a remainder of 0) by every digit in the number. For example, 128 is self divisible as it can be evenly divided by 1, 2, and 8. Similarly, all single digit numbers are also self divisible as they would just be divided by their only digit aka themselves and again leave no remainder.
Now that we’ve clarified what exactly self dividing numbers are, let’s move onto the goal of the problem. Basically, what we want to do is, given two boundary numbers, return every self dividing integer between them. For example, if we were given the boundaries of 1 and 22, we would want to return this array of self divisible numbers:
[1,2,3,4,5,6,7,8,9,11,12,15,22]One quick thing to note before we begin is that our lower and upper bounds will never be negative or greater than 10000.
The Solution: An Overview
To start this problem, I did what I always do and mapped out a psuedo-coded solution. For this solution I new that we would probably want to loop through every number between the left and right bounds, find those digits of those numbers, and check to see if the number is divisble by all of its digits. Then, if it wasn’t, we would remove that number from our list of possible numbers and at the end of the problem we could return that list.
While this overview does not go into great detail, I find that having a plan prior to me attempting the problem can really help me in the solving process as when I get flustered or lost I have a general overview to refer back to.
However, for the purposes of helping you understand how I approached solving this problem as well as with knowledge that I know have from actually solving the problem, I’m going to expand my overview a little into three more clearly defined steps.
First, I’m going to make an array containing all of the numbers between our left (lower) and right (upper) input bounds. Second, I’m going to create an object (aka a hash aka a hashmap aka a dictionary) where the keys are the numbers themselves and the values are the digits of its corresponding key. And finally, I’m going to loop through our object and delete any number wherein it is not evenly divisible by one of its digits.
So, keeping this plan in mind, let’s move onto solving this problem!
The Solution: Creating an array of numbers
The first part of our solution is definitely what I would consider to be the easiest as we will just be taking our left and right input bounds and creating an array with all of the integers between them.
To do this, we can write a simple for loop:
selfDividingNumbers = (left, right) => {
let allNums = []
for (let i = left; i <= right; i++) {
allNums.push(i)
}
}Now that we have this array created, let’s move on to the next step of our problem solving process!
The Solution: Creating an object of those same numbers
This next step in our solution might seem a little more complex, especially if you are not familiar with writing objects. But don’t worry, it’s really not too hard!
If you’d like a little bit more of an explanation of what exactly an object/hashmap is, I’ve written a post about it that I’d recommend you check out!
Basically, what we are going to is take each number from the array we made above and, using that number as our key, create corresponding values with that numbers digits. Since we are given the numbers as integers, I think the easiest way to get the digits will be to stringify and then split those numbers. While this make our values strings, and thus impossible to divide with, don’t worry we will correct this in our final step!
selfDividingNumbers = (left, right) => {
//step one: creating an array of all possible numbers
let allNums = []
for (let i = left; i <= right; i++) {
allNums.push(i)
} //step two: creating an object of all possible numbers
//plus their digits
let numsObj = {}
for (let j = 0; j < allNums.length; j++) {
numsObj[allNums[j]] = allNums[j].toString().split("")
}
}
The Solution: Our final step aka where we actually divide
Now that we’ve successfully completed the first two parts of our problem, we can move onto our third and final step. Here, we will be doing some unfortunate and that is creating a nested loop. So we are clear, this creates a potentially very slow algorithm with a runtime of O(n²). Obviously, this is not ideal and while I’m sure there are better ways of solving this problem (and I challenge you to find one!), today is the election and refactoring is not my top priority.
Anyway, now that we’ve acknowledged this issue with this solution, let’s write our final bit of code and complete our algorithm!
What are we are going to do is, as I said above, write a set of nested loops. The outer loop will loop through the keys of our numbers object, while the inner loop will give us access to each our digits in the corresponding values. Then, we can parseInt both the key and the values and see if they are evenly divisible. If not, we can delete the key-value pair from our object.
selfDividingNumbers = (left, right) => {
//step one: creating an array of all possible numbers
let allNums = []
for (let i = left; i <= right; i++) {
allNums.push(i)
} //step two: creating an object of all possible numbers
//plus their digits
let numsObj = {}
for (let j = 0; j < allNums.length; j++) {
numsObj[allNums[j]] = allNums[j].toString().split("")
}
//step three: looping through our objects keys and values
//to find what numbers are self dividing
for (let num in numsObj) {
for (let char of numsObj[num] {
if (parseInt(num) % parseInt(char) !== 0) {
delete numsObj[num]
}
}
}}
I want to quickly note that the outer loop uses a for in loop which is for iterating through objects, while the inner loop is using a for of loop which is for looping through arrays (which is what the values of the keys will be thanks to our split function!).
The Solution: Aren’t we done, yet?
If you are new to practicing algorithms you may not have realized that we have forgotten something vital to our solution and that is our return statement. While it would be nice (and in a way, basically correct) to just be able to return our numsObj that will contain only numbers that are self dividing. Unfortunately, the leetcode test cases expect an array of integers. In order to return that, we can write a simple map function that parseInt our they keys of our object and return exactly what we need to pass our tests!
selfDividingNumbers = (left, right) => {
//step one: creating an array of all possible numbers
let allNums = []
for (let i = left; i <= right; i++) {
allNums.push(i)
}//step two: creating an object of all possible numbers
//plus their digits
let numsObj = {}
for (let j = 0; j < allNums.length; j++) {
numsObj[allNums[j]] = allNums[j].toString().split("")
}
//step three: looping through our objects keys and values
//to find what numbers are self dividing
for (let num in numsObj) {
for (let char of numsObj[num] {
if (parseInt(num) % parseInt(char) !== 0) {
delete numsObj[num]
}
}
}
//NEVER FORGET TO RETURN!!!
return Object.keys(numsObj).map(num => parseInt(num))}
At last, we have successfully solved our algorithm! However, like I said above, this solution is not the best. So, I challenge anyone reading this to write a faster solution to this problem!
Good luck and happy coding!
