The Luhn Algorithm — Validating Numbers the Smart Way

04213

Simple Algorithms (4 Part Series)

1 Palindrome – Simple Algorithms for Programmers Looking for a Job: Part One
2 Latin Square – Simple Algorithms for Programmers Looking for a Job: Part Two
3 Triangle of Differences – Simple Algorithms for Programmers Looking for a Job: Part three
4 The Luhn Algorithm — Validating Numbers the Smart Way

When applying for jobs as a junior developer, one of the common algorithm questions you might encounter is the Luhn Algorithm. It’s simple, clever, and widely used in the real world, especially in banking and telecommunication. Understanding this algorithm not only helps you sharpen your logic skills but also gives you insight into how some real systems validate important information like credit card numbers.

What is the Luhn Algorithm?

The Luhn algorithm, also called the “modulus 10” algorithm or “mod 10”, is a checksum formula. It was developed in 1954 by Hans Peter Luhn, an engineer at IBM. The main purpose of this algorithm is to verify whether a sequence of numbers is valid, usually for identification or payment purposes.

While it does not protect against fraud (it’s not encryption), it helps to catch simple human errors such as a single digit mistyped or digits swapped by accident. This is extremely useful when working with long strings of numbers.

Where is it used?

The Luhn algorithm is widely used in real-life applications. It is used by credit card companies (Visa, Mastercard, American Express), in mobile phone IMEI numbers, and even in some national ID numbers. Whenever a form tells you “this card number is invalid” before you even click submit, it is probably using Luhn to validate it.

Problem Statement

You are given a string that represents a card number. The number may include spaces or dashes. Your task is to write a function that verifies whether this number is valid using the Luhn algorithm.

The function should return true if the number is valid and false otherwise.

Pseudocode

Before jumping into real code, let’s write down the logic of the Luhn algorithm in plain pseudocode: 

function isValidLuhn(number):
    clean the input by removing spaces and dashes
    reverse the cleaned number
    initialize total to 0
    for each digit in the reversed number:
        if the digit is in an even position (starting from 0):
            add the digit to total as is
        if the digit is in an odd position:
            double it
            if the result is greater than 9:
                subtract 9 from the result
            add that result to total
    if total modulo 10 is 0:
        return true (number is valid)
    else:
        return false (number is invalid)
function isValidLuhn(number):
    clean the input by removing spaces and dashes
    reverse the cleaned number
    initialize total to 0

    for each digit in the reversed number:
        if the digit is in an even position (starting from 0):
            add the digit to total as is
        if the digit is in an odd position:
            double it
            if the result is greater than 9:
                subtract 9 from the result
            add that result to total

    if total modulo 10 is 0:
        return true (number is valid)
    else:
        return false (number is invalid)
function isValidLuhn(number):
    clean the input by removing spaces and dashes
    reverse the cleaned number
    initialize total to 0

    for each digit in the reversed number:
        if the digit is in an even position (starting from 0):
            add the digit to total as is
        if the digit is in an odd position:
            double it
            if the result is greater than 9:
                subtract 9 from the result
            add that result to total

    if total modulo 10 is 0:
        return true (number is valid)
    else:
        return false (number is invalid)

Enter fullscreen mode Exit fullscreen mode

This pseudocode captures the essence of the algorithm and will guide us when implementing it in real programming languages.

Python: 

<span>def</span> <span>verify_card_number</span><span>(</span><span>card_number</span><span>):</span>
    <span>sum_of_odd_digits</span> <span>=</span> <span>0</span>
    <span>card_number_reversed</span> <span>=</span> <span>card_number</span><span>[::</span><span>-</span><span>1</span><span>]</span>
    <span>odd_digits</span> <span>=</span> <span>card_number_reversed</span><span>[::</span><span>2</span><span>]</span>
    <span>for</span> <span>digit</span> <span>in</span> <span>odd_digits</span><span>:</span>
        <span>sum_of_odd_digits</span> <span>+=</span> <span>int</span><span>(</span><span>digit</span><span>)</span>
    <span>sum_of_even_digits</span> <span>=</span> <span>0</span>
    <span>even_digits</span> <span>=</span> <span>card_number_reversed</span><span>[</span><span>1</span><span>::</span><span>2</span><span>]</span>
    <span>for</span> <span>digit</span> <span>in</span> <span>even_digits</span><span>:</span>
        <span>number</span> <span>=</span> <span>int</span><span>(</span><span>digit</span><span>)</span> <span>*</span> <span>2</span>
        <span>if</span> <span>number</span> <span>>=</span> <span>10</span><span>:</span>
            <span>number</span> <span>=</span> <span>(</span><span>number</span> <span>//</span> <span>10</span><span>)</span> <span>+</span> <span>(</span><span>number</span> <span>%</span> <span>10</span><span>)</span>
        <span>sum_of_even_digits</span> <span>+=</span> <span>number</span>
    <span>total</span> <span>=</span> <span>sum_of_odd_digits</span> <span>+</span> <span>sum_of_even_digits</span>
    <span>return</span> <span>total</span> <span>%</span> <span>10</span> <span>==</span> <span>0</span>
<span>def</span> <span>main</span><span>():</span>
    <span>card_number</span> <span>=</span> <span>'</span><span>4111-1111-4555-1141</span><span>'</span>
    <span>cleaned</span> <span>=</span> <span>card_number</span><span>.</span><span>replace</span><span>(</span><span>'</span><span>-</span><span>'</span><span>,</span> <span>''</span><span>).</span><span>replace</span><span>(</span><span>'</span><span> </span><span>'</span><span>,</span> <span>''</span><span>)</span>
    <span>if</span> <span>verify_card_number</span><span>(</span><span>cleaned</span><span>):</span>
        <span>print</span><span>(</span><span>'</span><span>VALID!</span><span>'</span><span>)</span>
    <span>else</span><span>:</span>
        <span>print</span><span>(</span><span>'</span><span>INVALID!</span><span>'</span><span>)</span>
<span>main</span><span>()</span>
<span>def</span> <span>verify_card_number</span><span>(</span><span>card_number</span><span>):</span>
    <span>sum_of_odd_digits</span> <span>=</span> <span>0</span>
    <span>card_number_reversed</span> <span>=</span> <span>card_number</span><span>[::</span><span>-</span><span>1</span><span>]</span>
    <span>odd_digits</span> <span>=</span> <span>card_number_reversed</span><span>[::</span><span>2</span><span>]</span>

    <span>for</span> <span>digit</span> <span>in</span> <span>odd_digits</span><span>:</span>
        <span>sum_of_odd_digits</span> <span>+=</span> <span>int</span><span>(</span><span>digit</span><span>)</span>

    <span>sum_of_even_digits</span> <span>=</span> <span>0</span>
    <span>even_digits</span> <span>=</span> <span>card_number_reversed</span><span>[</span><span>1</span><span>::</span><span>2</span><span>]</span>
    <span>for</span> <span>digit</span> <span>in</span> <span>even_digits</span><span>:</span>
        <span>number</span> <span>=</span> <span>int</span><span>(</span><span>digit</span><span>)</span> <span>*</span> <span>2</span>
        <span>if</span> <span>number</span> <span>>=</span> <span>10</span><span>:</span>
            <span>number</span> <span>=</span> <span>(</span><span>number</span> <span>//</span> <span>10</span><span>)</span> <span>+</span> <span>(</span><span>number</span> <span>%</span> <span>10</span><span>)</span>
        <span>sum_of_even_digits</span> <span>+=</span> <span>number</span>

    <span>total</span> <span>=</span> <span>sum_of_odd_digits</span> <span>+</span> <span>sum_of_even_digits</span>
    <span>return</span> <span>total</span> <span>%</span> <span>10</span> <span>==</span> <span>0</span>

<span>def</span> <span>main</span><span>():</span>
    <span>card_number</span> <span>=</span> <span>'</span><span>4111-1111-4555-1141</span><span>'</span>
    <span>cleaned</span> <span>=</span> <span>card_number</span><span>.</span><span>replace</span><span>(</span><span>'</span><span>-</span><span>'</span><span>,</span> <span>''</span><span>).</span><span>replace</span><span>(</span><span>'</span><span> </span><span>'</span><span>,</span> <span>''</span><span>)</span>

    <span>if</span> <span>verify_card_number</span><span>(</span><span>cleaned</span><span>):</span>
        <span>print</span><span>(</span><span>'</span><span>VALID!</span><span>'</span><span>)</span>
    <span>else</span><span>:</span>
        <span>print</span><span>(</span><span>'</span><span>INVALID!</span><span>'</span><span>)</span>

<span>main</span><span>()</span>
def verify_card_number(card_number):
    sum_of_odd_digits = 0
    card_number_reversed = card_number[::-1]
    odd_digits = card_number_reversed[::2]

    for digit in odd_digits:
        sum_of_odd_digits += int(digit)

    sum_of_even_digits = 0
    even_digits = card_number_reversed[1::2]
    for digit in even_digits:
        number = int(digit) * 2
        if number >= 10:
            number = (number // 10) + (number % 10)
        sum_of_even_digits += number

    total = sum_of_odd_digits + sum_of_even_digits
    return total % 10 == 0

def main():
    card_number = '4111-1111-4555-1141'
    cleaned = card_number.replace('-', '').replace(' ', '')

    if verify_card_number(cleaned):
        print('VALID!')
    else:
        print('INVALID!')

main()

Enter fullscreen mode Exit fullscreen mode

JavaScript: 

function verifyCardNumber(cardNumber) {
    const cleaned = cardNumber.replace(/[\s-]/g, '');
    const reversed = cleaned.split('').reverse();
    let total = 0;
    for (let i = 0; i < reversed.length; i++) {
        let digit = parseInt(reversed[i]);
        if (i % 2 === 1) {
            digit *= 2;
            if (digit > 9) digit -= 9;
        }
        total += digit;
    }
    return total % 10 === 0;
}
console.log(verifyCardNumber("4111-1111-4555-1141") ? "VALID!" : "INVALID!");
function verifyCardNumber(cardNumber) {
    const cleaned = cardNumber.replace(/[\s-]/g, '');
    const reversed = cleaned.split('').reverse();
    let total = 0;

    for (let i = 0; i < reversed.length; i++) {
        let digit = parseInt(reversed[i]);

        if (i % 2 === 1) {
            digit *= 2;
            if (digit > 9) digit -= 9;
        }

        total += digit;
    }

    return total % 10 === 0;
}

console.log(verifyCardNumber("4111-1111-4555-1141") ? "VALID!" : "INVALID!");
function verifyCardNumber(cardNumber) {
    const cleaned = cardNumber.replace(/[\s-]/g, '');
    const reversed = cleaned.split('').reverse();
    let total = 0;

    for (let i = 0; i < reversed.length; i++) {
        let digit = parseInt(reversed[i]);

        if (i % 2 === 1) {
            digit *= 2;
            if (digit > 9) digit -= 9;
        }

        total += digit;
    }

    return total % 10 === 0;
}

console.log(verifyCardNumber("4111-1111-4555-1141") ? "VALID!" : "INVALID!");

Enter fullscreen mode Exit fullscreen mode

Java: 

<span>public</span> <span>class</span> <span>LuhnCheck</span> <span>{</span>
    <span>public</span> <span>static</span> <span>boolean</span> <span>verifyCardNumber</span><span>(</span><span>String</span> <span>cardNumber</span><span>)</span> <span>{</span>
        <span>String</span> <span>cleaned</span> <span>=</span> <span>cardNumber</span><span>.</span><span>replaceAll</span><span>(</span><span>"[\\s-]"</span><span>,</span> <span>""</span><span>);</span>
        <span>int</span> <span>total</span> <span>=</span> <span>0</span><span>;</span>
        <span>boolean</span> <span>doubleDigit</span> <span>=</span> <span>false</span><span>;</span>
        <span>for</span> <span>(</span><span>int</span> <span>i</span> <span>=</span> <span>cleaned</span><span>.</span><span>length</span><span>()</span> <span>-</span> <span>1</span><span>;</span> <span>i</span> <span>>=</span> <span>0</span><span>;</span> <span>i</span><span>--)</span> <span>{</span>
            <span>int</span> <span>digit</span> <span>=</span> <span>Character</span><span>.</span><span>getNumericValue</span><span>(</span><span>cleaned</span><span>.</span><span>charAt</span><span>(</span><span>i</span><span>));</span>
            <span>if</span> <span>(</span><span>doubleDigit</span><span>)</span> <span>{</span>
                <span>digit</span> <span>*=</span> <span>2</span><span>;</span>
                <span>if</span> <span>(</span><span>digit</span> <span>></span> <span>9</span><span>)</span> <span>digit</span> <span>-=</span> <span>9</span><span>;</span>
            <span>}</span>
            <span>total</span> <span>+=</span> <span>digit</span><span>;</span>
            <span>doubleDigit</span> <span>=</span> <span>!</span><span>doubleDigit</span><span>;</span>
        <span>}</span>
        <span>return</span> <span>total</span> <span>%</span> <span>10</span> <span>==</span> <span>0</span><span>;</span>
    <span>}</span>
    <span>public</span> <span>static</span> <span>void</span> <span>main</span><span>(</span><span>String</span><span>[]</span> <span>args</span><span>)</span> <span>{</span>
        <span>String</span> <span>number</span> <span>=</span> <span>"4111-1111-4555-1141"</span><span>;</span>
        <span>System</span><span>.</span><span>out</span><span>.</span><span>println</span><span>(</span><span>verifyCardNumber</span><span>(</span><span>number</span><span>)</span> <span>?</span> <span>"VALID!"</span> <span>:</span> <span>"INVALID!"</span><span>);</span>
    <span>}</span>
<span>}</span>
<span>public</span> <span>class</span> <span>LuhnCheck</span> <span>{</span>

    <span>public</span> <span>static</span> <span>boolean</span> <span>verifyCardNumber</span><span>(</span><span>String</span> <span>cardNumber</span><span>)</span> <span>{</span>
        <span>String</span> <span>cleaned</span> <span>=</span> <span>cardNumber</span><span>.</span><span>replaceAll</span><span>(</span><span>"[\\s-]"</span><span>,</span> <span>""</span><span>);</span>
        <span>int</span> <span>total</span> <span>=</span> <span>0</span><span>;</span>
        <span>boolean</span> <span>doubleDigit</span> <span>=</span> <span>false</span><span>;</span>

        <span>for</span> <span>(</span><span>int</span> <span>i</span> <span>=</span> <span>cleaned</span><span>.</span><span>length</span><span>()</span> <span>-</span> <span>1</span><span>;</span> <span>i</span> <span>>=</span> <span>0</span><span>;</span> <span>i</span><span>--)</span> <span>{</span>
            <span>int</span> <span>digit</span> <span>=</span> <span>Character</span><span>.</span><span>getNumericValue</span><span>(</span><span>cleaned</span><span>.</span><span>charAt</span><span>(</span><span>i</span><span>));</span>
            <span>if</span> <span>(</span><span>doubleDigit</span><span>)</span> <span>{</span>
                <span>digit</span> <span>*=</span> <span>2</span><span>;</span>
                <span>if</span> <span>(</span><span>digit</span> <span>></span> <span>9</span><span>)</span> <span>digit</span> <span>-=</span> <span>9</span><span>;</span>
            <span>}</span>
            <span>total</span> <span>+=</span> <span>digit</span><span>;</span>
            <span>doubleDigit</span> <span>=</span> <span>!</span><span>doubleDigit</span><span>;</span>
        <span>}</span>

        <span>return</span> <span>total</span> <span>%</span> <span>10</span> <span>==</span> <span>0</span><span>;</span>
    <span>}</span>

    <span>public</span> <span>static</span> <span>void</span> <span>main</span><span>(</span><span>String</span><span>[]</span> <span>args</span><span>)</span> <span>{</span>
        <span>String</span> <span>number</span> <span>=</span> <span>"4111-1111-4555-1141"</span><span>;</span>
        <span>System</span><span>.</span><span>out</span><span>.</span><span>println</span><span>(</span><span>verifyCardNumber</span><span>(</span><span>number</span><span>)</span> <span>?</span> <span>"VALID!"</span> <span>:</span> <span>"INVALID!"</span><span>);</span>
    <span>}</span>
<span>}</span>
public class LuhnCheck {

    public static boolean verifyCardNumber(String cardNumber) {
        String cleaned = cardNumber.replaceAll("[\\s-]", "");
        int total = 0;
        boolean doubleDigit = false;

        for (int i = cleaned.length() - 1; i >= 0; i--) {
            int digit = Character.getNumericValue(cleaned.charAt(i));
            if (doubleDigit) {
                digit *= 2;
                if (digit > 9) digit -= 9;
            }
            total += digit;
            doubleDigit = !doubleDigit;
        }

        return total % 10 == 0;
    }

    public static void main(String[] args) {
        String number = "4111-1111-4555-1141";
        System.out.println(verifyCardNumber(number) ? "VALID!" : "INVALID!");
    }
}

Enter fullscreen mode Exit fullscreen mode

Real-World Applications

The Luhn algorithm is not just an exercise. It is used in many systems that need to validate identifiers quickly and reliably. Credit cards are the most famous example. Before a payment is even processed, the system checks whether the card number could be valid using the Luhn algorithm.

Phone manufacturers also use it to validate IMEI numbers, which are unique to each mobile device. Some government-issued identification numbers use similar validation techniques to reduce human error during registration.

Going Further

To go deeper into this topic, here are some interesting questions you can try to answer:

What changes would you make to generate a valid card number instead of just checking it?
Can you adapt this algorithm to detect other types of errors, like swapped digits?
What are other checksum algorithms used in the real world, and how do they compare to Luhn?
Can you implement the algorithm in a functional programming style using languages like Haskell or Scala?
How would you optimize your implementation for verifying millions of numbers quickly in a database?

The Luhn algorithm is a perfect example of how a small piece of logic can have a big impact in real systems. By practicing it, you’re not only preparing for coding interviews but also learning how developers build safer and more reliable applications.

Simple Algorithms (4 Part Series)

1 Palindrome – Simple Algorithms for Programmers Looking for a Job: Part One
2 Latin Square – Simple Algorithms for Programmers Looking for a Job: Part Two
3 Triangle of Differences – Simple Algorithms for Programmers Looking for a Job: Part three
4 The Luhn Algorithm — Validating Numbers the Smart Way

原文链接：The Luhn Algorithm — Validating Numbers the Smart Way

展开阅读全文
© 版权声明
文章版权声明 1、本网站名称：拾光赋
2、本站永久网址：https://www.blogs.ink
3、本网站的文章部分内容可能来源于网络，仅供大家学习与参考，如有侵权，请联系站长QQ：805375623进行删除处理。
4、本站一切资源不代表本站立场，并不代表本站赞同其观点和对其真实性负责。
5、本站一律禁止以任何方式发布或转载任何违法的相关信息，访客发现请向站长举报
6、本站资源大多存储在云盘，如发现链接失效，请联系我们我们会第一时间更新。

THE END
Python（EN）
# python# java# programming# javascript
喜欢就支持一下吧
点赞13 分享
love understands love; it needs no talk.
相爱的心息息相通，无需用言语倾诉
评论 抢沙发

请登录后发表评论

    暂无评论内容

文章目录
kity的头像-拾光赋
文章目录
今日剩余 68.0%
本周剩余 38.3%
本月剩余 42.3%
本年剩余 70.6%
最近评论
杀人蜂的头像-拾光赋

杀人蜂4天前0

我很好奇这个网站能提供什么
Vito的头像-拾光赋

Vito6个月前2

你就是我心中的那首忐忑，总是让我惊心动魄
Jason.Meng的头像-拾光赋钻石会员

Jason.Meng徽章-人气大使-拾光赋6个月前2

总是会在人生的不同阶段反复爱上大佬的文章~
每日一言
love understands love; it needs no talk.
相爱的心息息相通，无需用言语倾诉