How do I implement the Luhn algorithm?

Question

I am trying to create a program to validate 10 to 12 digit long number sequences based on the luhn algorithm, but my program keeps on telling me that every number is invalid even though they're not.

This number should be valid, but my code doesn't think so: 8112189876

This number should not be valid, which my program agrees with, as it thinks every number is invalid: 8112189875

Here is my code:

static void luhn(){
    System.out.print("Enter number to validate:\n");
    String pnr = input.nextLine();
    int length = pnr.length();
    int sum = 0;
    for (int i = 1, pos = length - 1; i < 10; i++, pos--){
        char tmp = pnr.charAt(pos);
        int num = tmp - 0
        int product;
        if (i % 2 != 0){
            product = num * 1;
        }
        else{
            product = num * 2;
        }
        if (product > 9)
            product -= 9;
        sum+= product;              
        boolean valid = (sum % 10 == 0);
        if (valid){
            System.out.print("Valid!\r");
        }
        else{
            System.out.print("Invalid!");
        }
    }
}

Fencing

ericlippert.com/2014/03/05/how-to-debug-small-programs -- you should step through this running program with a debugger. I wonder whether tmp has the value you expect. "1".charAt(0) is not equal to 1. Try Integer.parseInt(). – Shipp

int num = tmp - 0 Pretty sure this line returns the ASCII char value rather than the digit value, no? – Expostulate

You're also ignoring the first character. – Scottie

Answer 1

The first thing I see is that you have:

int num = tmp - 0

You should instead have:

int num = tmp - '0';

Secondly, you should be validating your sum outside of the for loop, because you only care about the sum after processing all the digits.

Thirdly, you are starting from the end of the number, and you are not including the first number of your string. Why not use i for both tasks?

Resulting (working) method:

static void luhn(){
  System.out.print("Enter number to validate:\n");
  String pnr = input.nextLine();
  // this only works if you are certain all input will be at least 10 characters
  int extraChars = pnr.length() - 10;
  if (extraChars < 0) {
    throw new IllegalArgumentException("Number length must be at least 10 characters!");
  }
  pnr = pnr.substring(extraChars, 10 + extraChars);
  int sum = 0;
  // #3: removed pos
  for (int i = 0; i < pnr.length(); i++){
    char tmp = pnr.charAt(i);
    // #1: fixed the '0' problem
    int num = tmp - '0';
    int product;
    if (i % 2 != 0){
      product = num * 1;
    }
    else{
      product = num * 2;
    }
    if (product > 9)
      product -= 9;
    sum+= product;              
  }
  // #2: moved check outside for loop
  boolean valid = (sum % 10 == 0);
  if (valid){
    System.out.print("Valid!\r");
  }
  else{
    System.out.print("Invalid!");
  }
}

---

Stylistically, this method would be more useful if, instead of method signature

static void luhn() {

it instead had method signature

static boolean luhn(String input) {

This easily allows your code to get the String from ANY source (a file, hardcoded, etc.) and do anything with the result (print a message as yours does, or do something else). Obviously you would move the System.out.print, input.nextLine(), and if(valid) bits of code outside of this method.

Full refactored program:

import java.util.Scanner;

public class Luhn {
  private static Scanner input;

  public static void main(String... args) {
    input = new Scanner(System.in);
    System.out.print("Enter number to validate:\n");
    String pnr = input.nextLine();
    boolean result = luhn(pnr);
    printMessage(result);
    input.close();
  }

  static boolean luhn(String pnr){
    // this only works if you are certain all input will be at least 10 characters
    int extraChars = pnr.length() - 10;
    if (extraChars < 0) {
      throw new IllegalArgumentException("Number length must be at least 10 characters!");
    }
    pnr = pnr.substring(extraChars, 10 + extraChars);
    int sum = 0;
    for (int i = 0; i < pnr.length(); i++){
      char tmp = pnr.charAt(i);
      int num = tmp - '0';
      int product;
      if (i % 2 != 0){
        product = num * 1;
      }
      else{
        product = num * 2;
      }
      if (product > 9)
        product -= 9;
      sum+= product;              
    }
    return (sum % 10 == 0);
  }

  private static void printMessage(boolean valid) {
    if (valid){
      System.out.print("Valid!\r");
    }
    else{
      System.out.print("Invalid!");
    }
  }
}

Lovett

Answer 2

use org.apache.commons.validator.routines.checkdigit.LuhnCheckDigit.LUHN_CHECK_DIGIT.isValid(number)

Maven Dependency:

<dependency>
    <groupId>commons-validator</groupId>
    <artifactId>commons-validator</artifactId>
    <version>1.5.1</version>
</dependency>

Juicy

Answer 3

I use this function in an app for checking card number validity :

public static boolean Check(String ccNumber)
    {
            int sum = 0;
            boolean alternate = false;
            for (int i = ccNumber.length() - 1; i >= 0; i--)
            {
                    int n = Integer.parseInt(ccNumber.substring(i, i + 1));
                    if (alternate)
                    {
                            n *= 2;
                            if (n > 9)
                            {
                                    n = (n % 10) + 1;
                            }
                    }
                    sum += n;
                    alternate = !alternate;
            }
            return (sum % 10 == 0);
    }

Hope it helps,

Baxy

Answer 4

If you use Java 10 or higher, you can use the following code:

public static boolean luhn(String s) {
    IntUnaryOperator sumDigits = n -> n / 10 + n % 10;
    var digits = s.chars()
                  .map(Character::getNumericValue)
                  .toArray();
    return IntStream.rangeClosed(1, digits.length)
                    .map(i -> digits.length - i)
                    .map(i -> i % 2 == 0 ? digits[i] : sumDigits.applyAsInt(digits[i] * 2))
                    .sum() % 10 == 0;
}

It's the functional approach to this algorithm.

Scantling

Answer 5

You should be subtracting '0' from tmp, not 0. Subtracting 0 returns the ASCII value, which you don't want.

Decker

Java's String, Character and char use Unicode/UTF-16, not ASCII. – Inextinguishable

Answer 6

Here's some functions I wrote to both calculate the check digit for a given number and to verify a given number sequence and extract the number from it.

To calculate the check digit for a given number:

/**
 * Generates the check digit for a number using Luhn's algorithm described in detail at the following link:
 * https://en.wikipedia.org/wiki/Luhn_algorithm
 *
 * In short the digit is calculated like so:
 * 1. From the rightmost digit moving left, double the value of every second digit. If that value is greater than 9,
 *    subtract 9 from it.
 * 2. Sum all of the digits together
 * 3. Multiply the sum by 9 and the check digit will be that value modulo 10.
 *
 * @param number the number to get the Luhn's check digit for
 * @return the check digit for the given number
 */
public static int calculateLuhnsCheckDigit(final long number) {
    int     sum       = 0;
    boolean alternate = false;
    String  digits    = Long.toString(number);

    for (int i = digits.length() - 1; i >= 0; --i) {
        int digit = Character.getNumericValue(digits.charAt(i)); // get the digit at the given index
        digit = (alternate = !alternate) ? (digit * 2) : digit;  // double every other digit
        digit = (digit > 9)              ? (digit - 9) : digit;  // subtract 9 if the value is greater than 9
        sum += digit;                                            // add the digit to the sum
    }

    return (sum * 9) % 10;
}

To verify a sequence of digits using Luhn's algorithm and extract the number:

/**
 * Verifies that a given number string is valid according to Luhn's algorithm, which is described in detail here:
 * https://en.wikipedia.org/wiki/Luhn_algorithm
 *
 * In short, validity of the number is determined like so:
 * 1. From the rightmost digit (the check digit) moving left, double the value of every second digit. The check
 *    digit is not doubled; the first digit doubled is the one immediately to the left of the check digit. If that
 *    value is greater than 9, subtract 9 from it.
 * 2. Sum all of the digits together
 * 3. If the sum modulo 10 is equal to 0, then the number is valid according to Luhn's algorithm
 *
 * @param luhnsNumber the number string to verify and extract the number from
 * @return an empty Optional if the given string was not valid according to Luhn's algorithm
 *         an Optional containing the number verified by Luhn's algorithm if the given string passed the check
 */
public static Optional<Long> extractLuhnsNumber(final String luhnsNumber) {
    int     sum       = 0;
    boolean alternate = true;
    Long    number    = Long.parseLong(luhnsNumber.substring(0, luhnsNumber.length() - 1));

    for (int i = luhnsNumber.length() - 1; i >= 0; --i) {
        int digit = Character.getNumericValue(luhnsNumber.charAt(i)); // get the digit at the given index
        digit = (alternate = !alternate) ? (digit * 2) : digit;       // double every other digit
        digit = (digit > 9)              ? (digit - 9) : digit;       // subtract 9 if the value is greater than 9
        sum += digit;                                                 // add the digit to the sum
    }

    return (sum % 10 == 0) ? Optional.of(number) : Optional.empty();
}

Helse

Answer 7

Newcomers to this post/question can check appropriate Wikipedia page for solution. Below is the Java code copy-pasted from there.

public class Luhn
{
        public static boolean check(String ccNumber)
        {
                int sum = 0;
                boolean alternate = false;
                for (int i = ccNumber.length() - 1; i >= 0; i--)
                {
                        int n = Integer.parseInt(ccNumber.substring(i, i + 1));
                        if (alternate)
                        {
                                n *= 2;
                                if (n > 9)
                                {
                                        n = (n % 10) + 1;
                                }
                        }
                        sum += n;
                        alternate = !alternate;
                }
                return (sum % 10 == 0);
        }
}

Unilingual

Answer 8

package randomNumGen;

public class JavaLuhnAlgorithm {

    public static void main(String[] args) {
        // TODO Auto-generated method stub




        validateCreditCardNumber("8112189876");
        String imei = "012850003580200";
        validateCreditCardNumber(imei);
    }

    private static void validateCreditCardNumber(String str) {

        int[] ints = new int[str.length()];
        for (int i = 0; i < str.length(); i++) {
            ints[i] = Integer.parseInt(str.substring(i, i + 1));
        }
        for (int i = ints.length - 2; i >= 0; i = i - 2) {
            int j = ints[i];
            j = j * 2;
            if (j > 9) {
                j = j % 10 + 1;
            }
            ints[i] = j;
        }
        int sum = 0;
        for (int i = 0; i < ints.length; i++) {
            sum += ints[i];
        }
        if (sum % 10 == 0) {
            System.out.println(str + " is a valid credit card number");
        } else {
            System.out.println(str + " is an invalid credit card number");
        }
    }

}

Whipstock