In the cs50 course (Harvard) there is a C programming problem to determine the correctness of a credit card number through the Luhn algorithm (credit.c). Let’s analyze this problem and show two more solutions.
So. Any credit card has a number printed on it, which is also stored in the database of the bank that issued the card. Credit card numbers are generated in such a way that they have some kind of “checksum” – a mathematical relationship between at least one number and others. This checksum allows you to quickly perform initial checks and detect typos on the client side without having to make a request to the server.
This is where the Luhn Algorithm (created by Hans Peter Lun of IBM) comes in handy, which allows you to check the validity of the card in this way:
- Starting from the end (from the penultimate digit), multiply every second digit by 2, and then add the numbers of these parts together;
- Add the sum to the sum of the digits that were not multiplied by 2;
- If the last digit of the sum is 0 (i.e. the sum modulo 10 is 0) – the card is valid.
Let’s take the VISA card number and select every second digit, starting from the penultimate digit:
4003600000000014
We will get numbers:
4 0 6 0 0 0 0 1
Let’s write these numbers in reverse, for convenience:
1 0 0 0 0 6 0 4
Multiply each of these numbers by 2:
1*2 + 0*2 + 0*2 + 0*2 + 0*2 + 6*2 + 0*2 + 4*2
We get:
2 + 0 + 0 + 0 + 0 + 12 + 0 + 8
Let’s add the numbers of these parts (i.e., not the parts themselves) together:
2 + 0 + 0 + 0 + 0 + 1 + 2 + 0 + 8 = 13
Now let’s add this sum (13) to the sum of the digits that were not multiplied by 2 (starting from the end):
13 + 4 + 0 + 0 + 0 + 0 + 0 + 3 + 0 = 20
Hooray! The last digit of the received number is 0 – the card is valid. Now let’s write a program that allows the user to enter the card number and find out if it is valid; and also what type of cards it belongs to.
To understand the card type: American Express uses 15 digit numbers, MasterCard uses 16 digit numbers, and Visa uses 13 and 16 digit numbers. All American Express numbers start with 34 or 37; most MasterCard numbers start with 51, 52, 53, 54, or 55 (they also have some other potential starting numbers); All Visa numbers start with 4.
This puzzle can be quite difficult for beginners, so if something didn’t work out for you, I’ll give you some tips to get started; Well, the solutions will be posted below. Be careful, spoilers 🙂
- First, consider how you will store your credit card number. It’s pretty big. We will not put it immediately into an array or a string, but put it into a long, long variable (spoiler: long long int; to see – select).
- further .. if it is not clear from which side to approach the task: copy (or print) the example with the card 4003600000000014. Keep it in front of your eyes all the time and just do what is written there 🙂
to begin with, for clarity, start writing a program using ordinary variables, and only then a spoiler: convert everything to arrays. - ВYou can borrow test credit card numbers to test the program from paypal.
Igroglaz’s solution. I work directly in my IDE so I don’t use the non-native cs50 library. This affects the fact that the input has to be filtered by handles. At Shtukentsia, this library is used in the solution. First I wanna share my solution which passed all my test, but wasn’t accepted by cs50 tests:
#include <stdio.h>
#include <limits.h>
/*
4003600000000014 x16
. . . . . . . .
400360000000001 x15
. . . . . . .
4003600000000 x13
. . . . . .
*/
int main(void)
{
long long int cc = 0; // cc number; could be 13, 15, 16 numbers
int first_multiply = 0;
int second_summ = 0;
int final_summ = 0;
printf("Enter your CC number:\n");
do
{
if (!scanf("%lld", &cc) || // scanf returns 1 if valid
(cc < (long long)100000000000 && !(cc > LLONG_MAX))) // min/max CC number
printf("INVALID\n");
while (getchar() != '\n') ; // clear buffer
}
while (cc < (long long)100000000000 && !(cc > LLONG_MAX)); // min/max CC number
// now get separate numbers (2nd starting from end)
// make array which contain 9 elements (we will use only 8)
int n[9]; for (int i = 0; i < 10; i++) n[i] = 0; // fill array with 0;
n[1] = (cc % 100) / 10;
n[2] = (cc % 10000) / 1000;
n[3] = (cc % 1000000) / 100000;
n[4] = (cc % 100000000) / 10000000;
n[5] = (cc % 10000000000) / 1000000000;
n[6] = (cc % 1000000000000) / 100000000000;
n[7] = (cc % 100000000000000) / 10000000000000;
n[8] = (cc % 10000000000000000) / 1000000000000000;
// multiplied x2 (`d` - doubled)
int d[9]; for (int i = 0; i < 10; i++) d[i] = 0; // fill array with 0;
d[1] = (n[1]*2);
d[2] = (n[2]*2);
d[3] = (n[3]*2);
d[4] = (n[4]*2);
d[5] = (n[5]*2);
d[6] = (n[6]*2);
d[7] = (n[7]*2);
d[8] = (n[8]*2);
// Extract number from 0 to 9 from doubled numbers with module (`m`).
// Sometimes we will have 1 digit, sometimes 2 (then one will be 1).
int m[9]; for (int i = 0; i < 10; i++) m[i] = 0; // fill array with 0;
for (int i = 1; i < 9; i++) // must lurk only at 8 (legit array)
{
if (d[i] > 10)
m[i] = (d[i] % 10) + 1; // as we need summ, we can add 1 right on
else if (d[i] == 10)
m[i] = 1;
else
m[i] = d[i];
}
// first half done:
first_multiply = m[1]+m[2]+m[3]+m[4]+m[5]+m[6]+m[7]+m[8];
// now take leftover digits from initial CC number
int x[9]; for (int i = 0; i < 10; i++) x[i] = 0; // fill array with 0;
x[1] = (cc % 10);
x[2] = (cc % 1000) / 100;
x[3] = (cc % 100000) / 10000;
x[4] = (cc % 10000000) / 1000000;
x[5] = (cc % 1000000000) / 100000000;
x[6] = (cc % 100000000000) / 10000000000;
x[7] = (cc % 10000000000000) / 1000000000000;
x[8] = (cc % 1000000000000000) / 100000000000000;
// done! now calculate:
second_summ = x[1]+x[2]+x[3]+x[4]+x[5]+x[6]+x[7]+x[8];
final_summ = first_multiply + second_summ;
if (final_summ % 10 == 0)
{
if (cc < (long long)10000000000000) // 13 digits
{
printf("VISA\n");
}
else if (cc < (long long)1000000000000000) // 15 digits
{
printf("AMEX\n");
}
else if (cc < (long long)10000000000000000) // 16 digits
{
if (n[8] == 4) // visa cc always starts with 4
printf("VISA\n");
else
printf("MCARD\n");
}
}
else
printf("Credit card INVALID\n");
getchar();
getchar();
}
Igroglaz’s second solution which were approved by cs50 tests:
#include <stdio.h>
#include <limits.h>
/*
4003600000000014 x16
. . . . . . . .
400360000000001 x15
. . . . . . .
4003600000000 x13
. . . . . .
*/
int main(void)
{
long long int cc = 0; // cc number; could be 13, 15, 16 numbers
int first_multiply = 0;
int second_summ = 0;
int final_summ = 0;
printf("Enter your CC number:\n");
do
{
scanf("%lld", &cc);
while (getchar() != '\n') ; // clear buffer
}
while (cc < (long long)100000000);
if (cc < (long long)1000000000000 || cc >= (long long)10000000000000000) // min/max CC number: error reporting
{
printf("INVALID\n");
return 0;
}
// now get separate numbers (2nd starting from end)
// make array which contain 9 elements (we will use only 8)
int n[9];
for (int i = 0; i < 10; i++)
{
n[i] = 0; // fill array with 0;
}
n[1] = (cc % 100) / 10;
n[2] = (cc % 10000) / 1000;
n[3] = (cc % 1000000) / 100000;
n[4] = (cc % 100000000) / 10000000;
n[5] = (cc % 10000000000) / 1000000000;
n[6] = (cc % 1000000000000) / 100000000000;
n[7] = (cc % 100000000000000) / 10000000000000;
n[8] = (cc % 10000000000000000) / 1000000000000000;
// multiplied x2 (`d` - doubled)
int d[9];
for (int i = 0; i < 10; i++)
{
d[i] = 0; // fill array with 0;
}
d[1] = (n[1] * 2);
d[2] = (n[2] * 2);
d[3] = (n[3] * 2);
d[4] = (n[4] * 2);
d[5] = (n[5] * 2);
d[6] = (n[6] * 2);
d[7] = (n[7] * 2);
d[8] = (n[8] * 2);
// Extract number from 0 to 9 from doubled numbers with module (`m`).
// Sometimes we will have 1 digit, sometimes 2 (then one will be 1).
int m[9];
for (int i = 0; i < 10; i++)
{
m[i] = 0; // fill array with 0;
}
for (int i = 1; i < 9; i++) // must lurk only at 8 (legit array)
{
if (d[i] > 10)
{
m[i] = (d[i] % 10) + 1; // as we need summ, we can add 1 right on
}
else if (d[i] == 10)
{
m[i] = 1;
}
else
{
m[i] = d[i];
}
}
// first half done:
first_multiply = m[1] + m[2] + m[3] + m[4] + m[5] + m[6] + m[7] + m[8];
// now take leftover digits from initial CC number
int x[9];
for (int i = 0; i < 10; i++)
{
x[i] = 0; // fill array with 0;
}
x[1] = (cc % 10);
x[2] = (cc % 1000) / 100;
x[3] = (cc % 100000) / 10000;
x[4] = (cc % 10000000) / 1000000;
x[5] = (cc % 1000000000) / 100000000;
x[6] = (cc % 100000000000) / 10000000000;
x[7] = (cc % 10000000000000) / 1000000000000;
x[8] = (cc % 1000000000000000) / 100000000000000;
// done! now calculate:
second_summ = x[1] + x[2] + x[3] + x[4] + x[5] + x[6] + x[7] + x[8];
final_summ = first_multiply + second_summ;
if (final_summ % 10 == 0)
{
if (cc < (long long)10000000000000) // 13 digits
{
printf("VISA\n");
}
else if (cc < (long long)1000000000000000 && // 15 digits
((cc >= (long long)340000000000000 && cc < (long long)350000000000000) || // starts with 34
(cc >= (long long)370000000000000 && cc < (long long)380000000000000))) // starts with 37
{
printf("AMEX\n");
}
else if (cc < (long long)10000000000000000) // 16 digits
{
if (n[8] == 4) // visa cc always starts with 4
{
printf("VISA\n");
}
else if (cc >= (long long)5100000000000000 && cc < (long long)5600000000000000) // MCARD starts with 51,52,53,54,55
{
printf("MASTERCARD\n");
}
else
{
printf("INVALID\n");
}
}
else
{
printf("INVALID\n");
}
}
else
{
printf("INVALID\n");
}
return 0;
}
Solution #2 (cheezy from Shtukentsia).
Hello, this is Stukensia. Realizing that the task was difficult, I completely lost faith in myself and resorted to tips from the Internet. But Igroglazu said that she made the whole decision herself, since we ourselves go through the course without prompting.
It turned out like this:
#include <cs50.h>
#include <stdio.h>
#include <string.h>
int main(void)
{
string cardtype="";
long long int cardnum = get_long("Card number:");
int i=0;
long long int lenth = cardnum;
long long int lenthcardname = cardnum;
long long int lenthcardcheck = cardnum;
// Check lenth of input cardnumber (VALID or NOT):
for (i=0; lenth>0; i++)
{
lenth=lenth/10;
}
printf("Lenth:%i\n",i);
if (i<13 || i>16)
{
cardtype="INVALID\n";
}
else
{
cardtype="OK, LENTH\n";
}
printf("Lenth check:%s\n",cardtype);
// Check card type (AMEX, VISA, MASTERCARD):
long long int firstnumcheck=lenthcardcheck;
if (i==15)
{
printf("AMEX\n");
}
else if (i==13)
{
printf("VISA\n");
}
else if (i==16)
{
firstnumcheck=firstnumcheck/1000000000000000;
if (firstnumcheck==4)
printf("VISA\n");
else
printf("MASTERCARD\n");
}
printf("%lld\n",firstnumcheck);
// Check Luhn algoruthm (VALID or NOT):
int numbers1;
int numbers2;
int firstdig;
int seconddig;
int sumnum1=0;
int sumnum2=0;
do
{
numbers1=cardnum%10;
cardnum=cardnum/10;
sumnum1+=numbers1;
numbers2=cardnum%10;
cardnum=cardnum/10;
numbers2=numbers2*2;
firstdig=numbers2/10;
seconddig=numbers2%10;
sumnum2+=firstdig+seconddig;
}
while(cardnum>0);
int sumnum;
sumnum=sumnum1+sumnum2;
if (sumnum%10==0)
{
printf("GOOD! VALID CARD\n");
}
else
printf("INVALID\n");
}
Then I had to confess everything and redo it from scratch. More details about this situation:
Shtukentsia’s solution is honest-cat:
After the previous fail, pulling myself together, I managed to solve the problem on my own using the module.
#include <cs50.h>
#include <stdio.h>
#include <string.h>
int main(void)
{
string cardtype="";
long long int cardnum = get_long("Card number:");
int i=0;
long long int lenth = cardnum;
long long int lenthcardname = cardnum;
long long int lenthcardcheck = cardnum;
// Check the Luhn Algorithm
int num1 = cardnum%10;
int num2 = ((cardnum%100)/10)*2;
int num3 = (cardnum%1000)/100;
int num4 = ((cardnum%10000)/1000)*2;
int num5 = (cardnum%100000)/10000;
int num6 = ((cardnum%1000000)/100000)*2;
int num7 = (cardnum%10000000)/1000000;
int num8 = ((cardnum%100000000)/10000000)*2;
int num9 = (cardnum%1000000000)/100000000;
int num10 = ((cardnum%10000000000)/1000000000)*2;
int num11 = (cardnum%100000000000)/10000000000;
int num12 = ((cardnum%1000000000000)/100000000000)*2;
int num13 = (cardnum%10000000000000)/1000000000000;
int num14 = ((cardnum%100000000000000)/10000000000000)*2;
int num15 = (cardnum%1000000000000000)/100000000000000;
int num16 = ((cardnum%10000000000000000)/1000000000000000)*2;
int num2dig1 = num2%10;
int num4dig1 = num4%10;
int num6dig1 = num6%10;
int num8dig1 = num8%10;
int num10dig1 = num10%10;
int num12dig1 = num12%10;
int num14dig1 = num14%10;
int num16dig1 = num16%10;
int sumnumdig1 = num2dig1+num4dig1+num6dig1+num8dig1+num10dig1+num12dig1+num14dig1+num16dig1;
int num2dig2 = (num2-num2dig1)/10;
int num4dig2 = (num4-num4dig1)/10;
int num6dig2 = (num6-num6dig1)/10;
int num8dig2 = (num8-num8dig1)/10;
int num10dig2 = (num10-num10dig1)/10;
int num12dig2 = (num12-num12dig1)/10;
int num14dig2 = (num14-num14dig1)/10;
int num16dig2 = (num16-num16dig1)/10;
int sumnumdig2 = num2dig2+num4dig2+num6dig2+num8dig2+num10dig2+num12dig2+num14dig2+num16dig2;
int sumnum1=sumnumdig1+sumnumdig2;
int sumnum2=num1+num3+num5+num7+num9+num11+num13+num15;
int sumnum=sumnum1+sumnum2;
printf("Sumnum= %d\n",sumnum);
// Check if card valid: lenth of cardnumber & AMEX, VISA, MASTERCARD:
long long int firstnumcheck=lenthcardcheck;
for (i=0; lenth>0; i++)
{
lenth=lenth/10;
}
printf("Lenth:%i\n",i);
if (i<13 || i>16)
{
cardtype="INVALID\n";
}
else
{
cardtype="OK, LENTH\n";
if (sumnum%10==0)
{
if (i==15)
{
printf("AMEX\n");
}
else if (i==13)
{
printf("VISA\n");
}
else if (i==16)
{
firstnumcheck=firstnumcheck/1000000000000000;
if (firstnumcheck==4)
printf("VISA\n");
else
printf("MASTERCARD\n");
}
printf("%lld\n",firstnumcheck);
printf("GOOD! VALID CARD\n");
}
else
printf("INVALID\n");
}
printf("Lenth check:%s\n",cardtype);
}
And this programme after checking bugs looks like this:
#include <cs50.h>
#include <stdio.h>
#include <string.h>
//Check typy of creditcard and if it's even valid
int main(void)
{
string cardtype = "INVALID\n";
long long int cardnum = get_long("Card number:");
int i = 0;
long long int lenth = cardnum;
long long int lenthcardname = cardnum;
long long int lenthcardcheck = cardnum;
// Check the Luhn Algorithm
// First use module to identify each number of card
int num1 = cardnum % 10;
int num2 = ((cardnum % 100) / 10) * 2;
int num3 = (cardnum % 1000) / 100;
int num4 = ((cardnum % 10000) / 1000) * 2;
int num5 = (cardnum % 100000) / 10000;
int num6 = ((cardnum % 1000000) / 100000) * 2;
int num7 = (cardnum % 10000000) / 1000000;
int num8 = ((cardnum % 100000000) / 10000000) * 2;
int num9 = (cardnum % 1000000000) / 100000000;
int num10 = ((cardnum % 10000000000) / 1000000000) * 2;
int num11 = (cardnum % 100000000000) / 10000000000;
int num12 = ((cardnum % 1000000000000) / 100000000000) * 2;
int num13 = (cardnum % 10000000000000) / 1000000000000;
int num14 = ((cardnum % 100000000000000) / 10000000000000) * 2;
int num15 = (cardnum % 1000000000000000) / 100000000000000;
int num16 = ((cardnum % 10000000000000000) / 1000000000000000) * 2;
int num2dig1 = num2 % 10;
int num4dig1 = num4 % 10;
int num6dig1 = num6 % 10;
int num8dig1 = num8 % 10;
int num10dig1 = num10 % 10;
int num12dig1 = num12 % 10;
int num14dig1 = num14 % 10;
int num16dig1 = num16 % 10;
// Find first sum of digits
int sumnumdig1 = num2dig1 + num4dig1 + num6dig1 + num8dig1 + num10dig1 + num12dig1 + num14dig1 + num16dig1;
// Find second sum of digits
int num2dig2 = (num2 - num2dig1) / 10;
int num4dig2 = (num4 - num4dig1) / 10;
int num6dig2 = (num6 - num6dig1) / 10;
int num8dig2 = (num8 - num8dig1) / 10;
int num10dig2 = (num10 - num10dig1) / 10;
int num12dig2 = (num12 - num12dig1) / 10;
int num14dig2 = (num14 - num14dig1) / 10;
int num16dig2 = (num16 - num16dig1) / 10;
int sumnumdig2 = num2dig2 + num4dig2 + num6dig2 + num8dig2 + num10dig2 + num12dig2 + num14dig2 + num16dig2;
int sumnum1 = sumnumdig1 + sumnumdig2;
int sumnum2 = num1 + num3 + num5 + num7 + num9 + num11 + num13 + num15;
int sumnum = sumnum1 + sumnum2; // Final sum of digits
// Check if card valid: lenth of cardnumber & AMEX, VISA, MASTERCARD:
long long int firstnumcheck = lenthcardcheck;
for (i = 0; lenth > 0; i++)
{
lenth = lenth / 10;
}
if (i < 13 || i > 16) // If cardlenth invalid
{
printf("INVALID\n");
}
else
{
cardtype = "OK, LENTH\n";
if (sumnum % 10 == 0) // Check if the last digit of final sum = 0
{
int amex_check = firstnumcheck / 10000000000000;
if (i == 15 && (amex_check == 34 || amex_check == 37)) // Check if it's AmericanExpress
{
printf("AMEX\n");
}
else if (i == 13) // Check if it's VISA by lenth
{
printf("VISA\n");
}
else if (i == 16) // Check if it's VISA or Mastercard by first numbers
{
int firstnumcheck_16 = firstnumcheck / 1000000000000000;
int secondnumcheck = firstnumcheck / 100000000000000;
if (firstnumcheck_16 == 4)
{
printf("VISA\n");
}
else if (secondnumcheck == 51 || secondnumcheck == 52 || secondnumcheck == 53 || secondnumcheck == 54 || secondnumcheck == 55)
{
printf("MASTERCARD\n");
}
else
{
printf("INVALID\n");
}
}
else
{
printf("INVALID\n");
}
}
else
{
printf("INVALID\n");
}
}
}