Luhn Check (Card Number Validation)

medium Strings

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

Best approachTime O(n)Space O(1)

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.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * 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)
  1. Which digit is doubled first?