While learning to code, more experienced programmers and senior developers will say that in addition to knowing coding languages, syntax, and general computer knowledge, having a firm understanding of algorithms will really help you in a coding interview. There are established algorithms out there in the world that exist to solve problems, and it's good to know they exist, when to use them, and how to implement them.
The Luhn Algorithm was created by Hans Peter Luhn, who was an IBM scientist, and patented in 1960. It's used to verify a string of numbers, and mostly it's used for credit card numbers a long with various IDs. The Wikipedia page for the algorithm has a list (unsure how up to date it is) of the types of IDs it's used for.
It takes a string of numbers, and starting right to left it doubles every other digit, then adds the digits up at the end. If the sum of all the digits ends in a 0 (i.e. it's divisible by 10), the number is valid. Otherwise, the number is invalid. This seems simple, but there is one extra step. If the doubled number is two digits (greater than 9), you replace the double number with the sum of it's two digits.
For example, if you double 6 you get 12. 12 is greater than 9 and is a two digit number. So instead of using 12 in your sum, you add it's two digits: 1 and 2. So you end up with 3.
If you didn't get that the first time you read this, that's okay. I didn't either when I was first reading about it. Luckily, James Hamblin has a fantastic video on Youtube that explains the algorithm with a credit card example, and he does a fantastic job at it. Below is the example he uses in the video.
As you can see, starting from the right and going to the left, we begin at 5. 5 is the first digit, so we leave it alone as the "Product."
The second number is 9, so we double that and get 18. But since 18 is greater than 10, we add the two digits instead. 1 + 8 = 9. Thus, 9 is the "Product" for 9.
The third number is 7, which we leave as is.
The fourth number is 8, which we double to make 16. Again, 16 is greater than 9. So we add 1 and 6, and we end up with 7, the "Product."
We continue to follow this pattern all the way through the end of the string of numbers. Then we sum all the numbers on our Product line. The sum of the "Product" numbers is 70, so this number is indeed valid!
Now what happens if we are missing one of these numbers? The Luhn Algorithm will be able to give us the correct number because of it's rules.
The current sum of the "Product" line is 73. We know that the furthest right number has to be multiplied by only 1, per the rules, and we don't have negative numbers. So we have to get our Product sum to 80. The difference we have to make up is 7, and the only way to get 7 with the weight of 1 is...you guessed it: 7!
So this is how the Luhn Algorithm works. In my next post, I'll write up how I went about doing this in Python from a freeCodeCamp course I took. Thanks for reading!