Credit Card Validation
Medium · rating 1300 · math, implementation
Credit card numbers are validated with the Luhn checksum: from the rightmost digit, double every second digit; if a doubled value exceeds 9 subtract 9; the total of all digits must be divisible by 10. Read a string of digits and print VALID or INVALID.
Editorial
Credit Card Validation uses the Luhn algorithm, a checksum that catches most single-digit typos and adjacent transpositions — the same check that guards real card numbers.
Approach
Starting from the rightmost digit, double every second digit; if a doubled value exceeds 9, subtract 9 (the same as summing its two digits). Sum everything — the number is valid when the total is divisible by 10.
total = 0; double = False
for d in reversed(digits):
if double:
d *= 2
if d > 9: d -= 9
total += d
double = not double
return total % 10 == 0Complexity
Time: O(n). Space: O(1).