<< Week 5: Misc 02 | View Solution on GitHub | Week 7: Linked Lists >>
Image: GeeksForGeeks
Welcome back to Whiteboarding in Python, where every week, I break down one problem from data structures, algorithms, and general head-scratchers into clean, easy-to-understand solutions.
I currently work as a TA at a coding bootcamp, and I love the determination of my students. Over the course of twelve weeks, they're expected to go from very little or no coding experience to having published three full stack web apps. They grow up so fast! (I'm not just joking, it's really extraordinary, and I'm proud of you all). But week one is a doozy, especially for those who have almost no JavaScript experience, and are thrown into it at full force.
Well, for me, it was certainly interesting when I didn't understand that Java, which I learned at university, is a completely different language from JavaScript, which is the language for pretty much all front end web development. "Wow!" I thought to myself on week one. "There sure have been a lot of updates since I learned 'JavaScript'!" (admissions people, *please* take notice). But, the fact that I had a good foundation of CS principles really helped. Once you understand the theory behind well implemented, clean code, learning a new language is just a matter of taking the old one and giving it some new pants. Or a hat. Some sort of similar metaphor.
This is what we're going to do today. Some of you may have seen this problem, a very tricky JS problem that is sometimes given as homework in the first week. By now, you may not think it so difficult, but when you first started, it may have seemed quite daunting. Today, we'll quickly walk through the solution in JS, and then, I'll show you how to convert it to Python. Hopefully this will give you some insight in this "pants trick" I just described, i.e. how to take the same concepts and reapply them in a new language.
Let's look at the problem:
# A number is pandigital if it has digits 1-n for a number
n digits long.
# Given a number, return whether or not it is pandigital.
First we have to get over the problem of "What the heck does pandigital mean?" The prompt states a number, presumably an integer, can be called pandigital if it has digits 1-N for a number N digits long. Meaning, if a number is 5 digits long, it must contain the digits 1, 2, 3, 4 and 5. Here's some sample output:
print(is_pandigital(321))
# -> True
print(is_pandigital(123465))
# -> True
print(is_pandigital(12765))
# -> False
Solution #1: JavaScript
First of all, we'll define a method isPandigital() that takes in one argument, the number, which we'll call num.
function isPandigital(num) {
}
Next, let's think about the solution. We have to compare digits, which is entirely possible to do while keeping the number as an integer. However, it will take a lot of math, i.e. separating the digits using a compination of division and mod operations. For instance, if we have 1234 and we want to get the 2, we would call num % 1000 to get the last 3 digits, and then use Math.floor(num/100) to get rid of the 3 and 4. So it isn't impossible, but it may seem like a lot if you just learned to code and don't have a math-heavy background.
Instead, we can convert the number into a string and then into a list of characters. This way, we can easily compare the digits. Here's how we do that in JavaScript:
function isPandigital(num) {
num = num.toString().split("");
}
There's a method in JavaScript called toString() that parses other types into a String. A similar method called parseInt() changes a string into its integer equivalent. Then, we call the .split() method, which separates a string with along the divider character, passed as an argument. We'll pass an empty string, which tells JavaScript to give each character its own spot in the array. You can try to console log num on the next line to see what it looks like, which should be something like 123 => ['1', '2', '3'].
There are a couple ways you could go from here. Here's something you can always ask: would this problem be easier if the string were sorted? If we have a number 123, we know exactly what it would have to look like if it were pandigital– each digit counting up from 1. It would look the same every time, whether we started with 321 or 213, etc. JavaScript has a .sort() method similar to Python, so we'll sort the array and resave it to the num variable. I'll concatenate this to the previous line.
function isPandigital(num) {
num = num.toString().split("").sort();
}
Next, we need an array to compare values. The galaxy brain way to do this is simply make an array with every value:
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];
However, there's a simpler solution. In our sorted array, each item has an index that starts at 0 and goes to the length minus one. '1' is at index 0, '2'is at index 1, and so on. So, all we need to do is loop through the list and check that each value is equal to its index plus one:
for (let i=0; i < num.length; i++) {
if (num[i] != i+1) {
return false;
}
}
If the number at the index is not equal to the index plus one, we return false because the number is not pandigital. Otherwise, if we make it through the whole array and find no problems, we'll return true. Altogether:
isPandigital.js
function isPandigital(num) {
num = num.toString().split("").sort();
console.log(num);
for (let i=0; i < num.length; i++) {
if (num[i] != i+1) {
return false;
}
}
return true;
}
And that's it for JavaScript. If you console log the return value of isPandigital(12345), you should get true.
Solution 2: Python
Converting the solution shouldn't be too difficult, since we already have the problem solved and working. All that's left is a few differences in JS and Python syntax. You can try rewriting the code line by line, or start from scratch.
The function declaration is a simple syntax difference, we get rid of the word function and add a def, semicolons and brackets are going to disappear, etc.
def is_pandigital(num):
pass
If you remember, we started by converting the number into a string. Python has typecasting methods that simply involve taking the type and putting parentheses around it:
def is_pandigital(num):
num = str(num)
Now we'll make a list of each character in the string. I've said it in previous posts, and I'll say it again: this comes up a lot, and it would help to know it by heart. Does this look familiar: [char for char in s]? The inline for loop returns a character for each character in the string, and the brackets cast those values into a list. This is how it will look to separate each digit:
num = [digit for digit in str(num)]
Next, we want to sort the list. For JavaScript, we called .sort() and reassigned it to the num variable:
num = num.sort()
If you try this in Python, you might notice something strange happened.
>>> num = [2,3,1,4]
>>> num = num.sort()
>>> print(num)
None
Now our list is equal to None! This is because the .sort() methods in Python and JavaScript are a little different. JavaScript returns a sorted version of the list, and Python alters the original list, and has no return value. So, we just have to call .sort() without reassigning num.
num.sort()
Next, we iterate over the list. To loop through each index in a list, instead of each value, we use the range() function and pass it the length of the list.
for i in range(len(num)):
Finally, we have our if statement, which looks largely the same, minus some parentheses and curly braces. Remember that we have to cast the digit back to an integer with int() in order to evaluate it.
for i in range(len(num)):
if int(num[i]) != (i + 1):
return False
Finally, we return True outside the for loop. Remember that True and False are capitalized in Python.
def is_pandigital(num):
num = [digit for digit in str(num)]
num.sort()
print(num)
for i in range(len(num)):
if int(num[i]) != (i + 1):
return False
return True
And there you have it! Our method has been successfully converted into Python. You may ask, how did I know that .sort() works differently in Python, or that the method to turn a number into a string is str() instead of toString()? The answer is, if you don't know, look it up! Googling "cast to string python" should give you something. Apart from that, simply playing around and testing different cases works just as well. Just a few adjustments here and there, and our method is fully functional.
Solution 3: More Optimal Python
Let's talk time complexity. Our last solution used the sort() method, and if you remember, its average and worst case complexity is O(N log N). How would we do better, say, with O(N) complexity?
If we're allowed to use additional data structures, you might think of using a list to store the count of each letter. The digits can each be represented by an index where each index is that digit minus one. Then we simply loop through each digit in the number, adding a count of 1, or True, or some truthy value. If a truthy value already exists, or the number falls outside the index range, we know the number is not pandigital.
For example, let's say the number is 121. The method loops through each digit, putting each digit at its value minus one. So the list puts True in the 0th spot for the first '1', and True in the 1st slot for the '2', and when it reaches the second '1', the value at index 0 is already True, so we know the number is not pandigital.
Let's go about implementing this solution. To begin, we'll start by casting num to a string. This way, we can iterate over each character in the for loop quite easily. What would happen if we tried to loop over num as an int? Well, the number of 12345 would cause the program to run 12,345 times, which wouldn't be good.
def is_pandigital2(num):
num = str(num)
Now lets make our list counter, where we count the occurence of each digit. In JavaScript, we could just initialize it as an empty list, and then if we tried to set index 3 to true, it would simply extend the array with 0 values. Here's the output I got in Node:
> arr = [];
> arr[3] = true;
> console.log(arr);
[ <3 empty items>, true ]
Cool. Let's try the same in Python.
>>> lis = []
>>> lis[3] = True
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
IndexError: list assignment index out of range
Come on, Python! How could you betray us in our time of need? So instead, we'll have to make a list of False values that's the same length as our string. How will we do that? It's easy! Python allows for list multiplication. We simply multiply a list with one value, False, times the length we need it to be.
counter = [False] * len(num)
For example, if the number is 123, counter will be initialized to [False, False, False], which is exactly what we want.
Next, the for loop. We're looping over each character in the string, so it's pretty simple to set up. The first thing I'll do afterwards is cast the digit back to an integer so we can evaluate it.
for digit in num:
digit = int(digit)
For each digit, we want to check 1. that it's not outside the range and 2. that it hasn't been counted yet. So, we implement an if statement:
for digit in num:
digit = int(digit)
if digit > len(num) or counter[digit - 1]:
return False
Finally, we set the counter for that digit to be true.
for digit in num:
digit = int(digit)
if digit > len(num) or counter[digit - 1]:
return False
else:
counter[digit - 1] = True
Now we just have to return True outside of the for loop.
def is_pandigital2(num):
num = str(num)
counter = [False] * len(num)
for digit in num:
digit = int(digit)
if digit > len(num) or counter[digit - 1]:
return False
else:
counter[digit - 1] = True
return True
This will work as expected if we pass in the number 12645. If you print counter before the line that returns False, it should give you: [True, True, False, False, False], where the digits 1 and 2 were counted, but 6 fell outside the range.
That's it for this week (although there is an edge case we missed, can you find it?). Next week, we'll return to data structures to look at Linked Lists! Also, shout out to Signe Bergman for rotating the glasses emoji on the python photo!
<< Week 5: Misc 02 | View Solution on GitHub | Week 7: Linked Lists >>
Sheamus Heikkila is formerly a Teaching Assistant at General Assembly Seattle. This blog is not associated with GA.
Top comments (2)
All your solutions seem exceedingly complex. I would solve this problem with the following O(n) algorithm:
Create a set with the numbers 1 - N and a second set from the digits in the number given, if both sets are egal then the number is pandigital.
You're right! I just added this solution to the Github; it looks much cleaner. We might cover sets in a future article. Thank you, sir!