Luhn Check (Card Number Validation)
Problem
Read a number as a string of digits. Check it with the Luhn algorithm: from the right, double every second digit (if the result is above 9, subtract 9), add all digits, and the number is valid when the sum is a multiple of 10. Print true or false.
Constraints
- 1 <= length <= 30, digits only
Examples
Input
4539578763621486
Output
true
Solutions
The Luhn check catches most typing errors (one wrong digit or two swapped digits). Real credit card numbers use it. We walk from the right and double every second digit.
/*
* Problem : Process one line of text.
* Input : One line of text.
* Output : true or false.
* Approach: Walk from the right.
* Time : O(n)
* Space : O(1)
* Java : 8 or newer.
*/
import java.util.Scanner;
public class Main {
// This method solves the task. It receives the input and returns the answer.
static boolean solve(String s) {
// Step 1: The sum starts at 0.
int sum = 0;
// Step 2: Go from the last digit to the first digit. position 0 is the last digit.
for (int i = s.length() - 1, position = 0; i >= 0; i--, position++) {
int digit = s.charAt(i) - '0';
// Step 3: Double every second digit. If the result is above 9, subtract 9.
if (position % 2 == 1) {
digit = digit * 2;
if (digit > 9) {
digit = digit - 9;
}
}
// Step 4: Add the digit to the sum.
sum = sum + digit;
}
// Step 5: The number is valid when the sum is a multiple of 10.
return sum % 10 == 0;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s = scanner.hasNextLine() ? scanner.nextLine() : "";
System.out.println(solve(s));
}
}
Hints (1)
- Which digit is doubled first?