Table of contents
1.
Introduction 
2.
Overview of the algorithm:
3.
Code Implementation
3.1.
C++
3.2.
Java
3.3.
Python
4.
Frequently Asked Questions
4.1.
Can the Luhn algorithm detect all types of errors in a number?
4.2.
Is the Luhn algorithm foolproof in validating identification numbers?
4.3.
Can the Luhn algorithm be used for numbers other than identification numbers?
5.
Conclusion
Last Updated: Aug 13, 2024
Easy

Luhn Algorithm

Author Rahul Singh
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction 

The Luhn algorithm is a simple checksum formula used to validate various identification numbers, such as credit card numbers, IMEI numbers, and Canadian Social Insurance Numbers. It was created by IBM scientist Hans Peter Luhn in the 1950s. This algorithm helps detect accidental errors that may occur during the manual entry of these numbers. 

Luhn Algorithm

In this article, we will learn how the Luhn algorithm works & will see its code implementation.

Overview of the algorithm:

The Luhn algorithm, also known as the modulus 10 or mod 10 algorithm, is a simple checksum formula that verifies the accuracy of an identification number. The algorithm performs a series of calculations on the digits of the number & determines if it is valid based on the result.

Let’s see how this algorithm works:

1. Start from the rightmost digit & move left, doubling the value of every second digit. If the doubled value is greater than 9, subtract 9 from the result.
 

2. Sum up all the digits, including the unmodified digits & the results from step 1.
 

3. If the total sum is divisible by 10, the number is valid according to the Luhn algorithm. Otherwise, the number is invalid.


For example, let's consider the number "7992739871". Applying the Luhn algorithm:
 

- Double every second digit from the right: 7 18 9 4 7 6 9 16 7 2

- Subtract 9 from any doubled digit greater than 9: 7 9 9 4 7 6 9 7 7 2

- Sum up all the digits: 7 + 9 + 9 + 4 + 7 + 6 + 9 + 7 + 7 + 2 = 67

- Since 67 is not divisible by 10, the number is invalid.

This algorithm is widely used to validate credit card numbers, IMEI numbers, & other identification numbers to catch accidental errors during manual entry or transmission.

Code Implementation

  • C++
  • Java
  • Python

C++

#include <iostream>
#include <string>
#include <cctype> // For isdigit function

bool isValid(const std::string& number) {
int sum = 0;
bool isOddIndex = false;

// Check if the input contains only digits
for (char c : number) {
if (!std::isdigit(c)) {
return false; // Return false if any non-digit character is found
}
}

for (int i = number.size() - 1; i >= 0; i--) {
int digit = number[i] - '0';

if (isOddIndex) {
digit *= 2;
if (digit > 9) {
digit -= 9;
}
}

sum += digit;
isOddIndex = !isOddIndex;
}

return (sum % 10 == 0);
}

int main() {
std::string cardNumber;
std::cout << "Enter the card number: ";
std::cin >> cardNumber;

if (isValid(cardNumber)) {
std::cout << "The card number is valid." << std::endl;
} else {
std::cout << "The card number is invalid." << std::endl;
}

return 0;
}
You can also try this code with Online C++ Compiler
Run Code

Java

import java.util.Scanner;

public class LuhnAlgorithm {

public static boolean isValid(String number) {
int sum = 0;
boolean isOddIndex = false;

// Check if the input contains only digits
for (char c : number.toCharArray()) {
if (!Character.isDigit(c)) {
return false; // Return false if any non-digit character is found
}
}

for (int i = number.length() - 1; i >= 0; i--) {
int digit = number.charAt(i) - '0';

if (isOddIndex) {
digit *= 2;
if (digit > 9) {
digit -= 9;
}
}

sum += digit;
isOddIndex = !isOddIndex;
}

return (sum % 10 == 0);
}

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("Enter the card number: ");
String cardNumber = scanner.nextLine();

if (isValid(cardNumber)) {
System.out.println("The card number is valid.");
} else {
System.out.println("The card number is invalid.");
}

scanner.close();
}
}
You can also try this code with Online Java Compiler
Run Code

Python

def is_valid(number: str) -> bool:
if not number.isdigit():
return False

sum = 0
is_odd_index = False

for digit in reversed(number):
digit = int(digit)

if is_odd_index:
digit *= 2
if digit > 9:
digit -= 9

sum += digit
is_odd_index = not is_odd_index

return sum % 10 == 0

# Example usage
card_number = input("Enter the card number: ")
if is_valid(card_number):
print("The card number is valid.")
else:
print("The card number is invalid.")
You can also try this code with Online Python Compiler
Run Code

 

Output

Enter the card number: 5
The card number is invalid.

Frequently Asked Questions

Can the Luhn algorithm detect all types of errors in a number?

No, the Luhn algorithm can only detect accidental single-digit errors & transpositions of adjacent digits. It cannot detect other types of errors.

Is the Luhn algorithm foolproof in validating identification numbers?

While the Luhn algorithm is effective in catching common errors, it is not foolproof. It is still possible for a number to pass the Luhn check but be invalid.

Can the Luhn algorithm be used for numbers other than identification numbers?

Yes, the Luhn algorithm can be applied to any number where error detection is needed, not just identification numbers.

Conclusion

In this article, we discussed the Luhn algorithm, a simple checksum formula used to validate various identification numbers. We learned how the algorithm works by doubling every second digit from the right, subtracting 9 from doubled digits greater than 9, & checking if the sum of all digits is divisible by 10. At the end we gave code examples in C++, Python, Java language.

You can also check out our other blogs on Code360.

Live masterclass