Statistics

Problem Statement for "ViscoverExpress"

Problem Statement

The credit card numbers on most major credit cards have a similar format. We will consider credit cards issued by the hypothetical Viscover Express company, but real credit cards differ only slightly.

A Viscover Express number is 16 digits long: a fixed prefix 3014, followed by an 11-digit individual account number, followed by a single check digit. The check digit is used to guard against data entry errors, and is calculated from the other 15 digits by the following algorithm:

  1. Double every second digit, starting with the leftmost. (For example, 7 would become 14.)
  2. Sum all the individual digits in the results of step 1. (For example, 14 would contribute 1+4=5 to the sum.)
  3. Sum all the remaining digits in the original number, and add to the result of step 2.
  4. Choose the check digit such that the sum of the check digit and the result of step 3 is a multiple of 10.
For example, starting with the 15-digit number 301412345678901 we would calculate the check digit as follows:
  1. Doubling 3,1,1,3,5,7,9,1 gives 6,2,2,6,10,14,18,2.
  2. Summing the individual digits gives 6+2+2+6+(1+0)+(1+4)+(1+8)+2 = 33.
  3. Summing the remaining digits in the original number gives 0+4+2+4+6+8+0 = 24.
  4. 33 + 24 = 57 so, to get a multiple of 10, we make the check digit 3.
The complete number is 3014123456789013.

When entering a credit card number, the two most common errors are single digit errors, in which a single digit is entered as a different digit, and transposition errors, in which two adjacent digits are entered in reverse order. You can detect most data entry errors by recalculating the check digit from the first 15 digits, and comparing it to the check digit that was actually entered. If they do not match, the card number is invalid.

Given a 16-digit number, assume that the user made at most one entry error, which could be either a single digit error or a transposition error, and calculate the set of valid numbers that the user might have intended. For example, if the user entered 3041123456789013, you would calculate that the only valid number that the user might have intended was 3014123456789013 (with the third and fourth digits transposed).

Create a class ViscoverExpress with a method possibleMatches that takes a 16-digit credit card number (as a String) and returns the set of valid credit card numbers that user might have intended (under the assumption that there was at most one entry error). The set is represented as a String[] in increasing order. Note that the set may be empty.

Definition

Class:
ViscoverExpress
Method:
possibleMatches
Parameters:
String
Returns:
String[]
Method signature:
String[] possibleMatches(String number)
(be sure your method is public)

Constraints

  • number contains exactly 16 characters, each of which is a digit ('0'-'9').

Examples

  1. "3041123456789013"

    Returns: { "3014123456789013" }

    The example above. The third and fourth digits were transposed. No other errors are possible because the prefix is required to be 3014.

  2. "3014000000000008"

    Returns: { "3014000000000008" }

    The number is correct as is. Any error would also change the check digit (except for errors that don't make any visible change to the number, like transposing two 0s).

  3. "3014123456789013"

    Returns: { "3014123456780913", "3014123456789013" }

    The number is valid as is, but the 9 and 0 could also have been transposed.

  4. "2014123456789012"

    Returns: { }

    No matches possible.

  5. "3014123451234555"

    Returns: { "3014121451234555", "3014123051234555", "3014123451034555", "3014123451232555", "3014123451234155", "3014123451234551", "3014123451234585", "3014123451294555", "3014123457234555", "3014123481234555", "3014183451234555", "3014423451234555" }

  6. "3114646473829123"

    Returns: { "3014646473829123" }

  7. "0314673589349976"

    Returns: { }

  8. "3015477832415868"

    Returns: { "3014577832415868" }

  9. "0000000000000000"

    Returns: { }

  10. "3014102398471438"

    Returns: { "3014102098471438", "3014102338471438", "3014102395471438", "3014102398417438", "3014102398441438", "3014102398471138", "3014102398471435", "3014102398471468", "3014102398479438", "3014102398771438", "3014105398471438", "3014172398471438", "3014902398471438" }

  11. "3014090990909090"

    Returns: { "3014030990909090", "3014090390909090", "3014090960909090", "3014090990609090", "3014090990906090", "3014090990909060", "3014090990909094", "3014090990909490", "3014090990949090", "3014090994909090", "3014092990909090", "3014290990909090" }

  12. "3014314159265358"

    Returns: { "3014304159265358", "3014314059265358", "3014314109265358", "3014314158265358", "3014314159255358", "3014314159260358", "3014314159265258", "3014314159265308", "3014314159265357", "3014314159665358", "3014318159265358", "3014714159265358" }

  13. "3025839273847519"

    Returns: { }

  14. "3014274829164537"

    Returns: { "3014214829164537", "3014247829164537", "3014271829164537", "3014274229164537", "3014274823164537", "3014274829104537", "3014274829161537", "3014274829164507", "3014274829164531", "3014274829164937", "3014274829364537", "3014274849164537", "3014474829164537" }

  15. "3014090990900903"

    Returns: { "3014009990900903", "3014090909900903", "3014090990090903", "3014090990900093", "3014090990900903", "3014090990909003", "3014090999000903", "3014099090900903", "3014900990900903" }

  16. "3014975312468021"

    Returns: { "3014795312468021", "3014875312468021", "3014955312468021", "3014975112468021", "3014975302468021", "3014975310468021", "3014975312368021", "3014975312448021", "3014975312467021", "3014975312468011", "3014975312468029", "3014975312468201", "3014975312468821", "3014975312486021", "3014975314268021", "3014979312468021" }

  17. "3010412390812942"

    Returns: { "3014012390812942" }

  18. "3014235478125867"

    Returns: { "3014235478125867" }

  19. "3014010203040506"

    Returns: { "3014010200040506", "3014010203010506", "3014010203040206", "3014010203040503", "3014010203040560", "3014010203040586", "3014010203048506", "3014010203840506", "3014010283040506", "3014010903040506", "3014018203040506", "3014080203040506", "3014810203040506" }

  20. "3014122333444455"

    Returns: { "3014022333444455", "3014102333444455", "3014121333444455", "3014122133444455", "3014122323444455", "3014122331444455", "3014122333344455", "3014122333424455", "3014122333443455", "3014122333444255", "3014122333444453", "3014122333444495", "3014122333444545" }

  21. "3014199520001989"

    Returns: { "3014119520001989", "3014195520001989", "3014199520001189", "3014199520001981", "3014199520001999", "3014199520002989", "3014199520021989", "3014199520101989", "3014199522001989", "3014199530001989", "3014199720001989", "3014299520001989" }

  22. "3014757575757575"

    Returns: { "3014577575757575", "3014657575757575", "3014737575757575", "3014755775757575", "3014756575757575", "3014757375757575", "3014757557757575", "3014757565757575", "3014757573757575", "3014757575577575", "3014757575657575", "3014757575737575", "3014757575755775", "3014757575756575", "3014757575757375", "3014757575757557", "3014757575757565", "3014757575757573", "3014757575757755", "3014757575775575", "3014757577557575", "3014757755757575", "3014775575757575" }

  23. "3014757575757575"

    Returns: { "3014577575757575", "3014657575757575", "3014737575757575", "3014755775757575", "3014756575757575", "3014757375757575", "3014757557757575", "3014757565757575", "3014757573757575", "3014757575577575", "3014757575657575", "3014757575737575", "3014757575755775", "3014757575756575", "3014757575757375", "3014757575757557", "3014757575757565", "3014757575757573", "3014757575757755", "3014757575775575", "3014757577557575", "3014757755757575", "3014775575757575" }

  24. "3014000000000040"

    Returns: { "3014000000000040" }

  25. "3014123484935842"

    Returns: { "3014123484535842", "3014123484935042", "3014123484935802", "3014123484935844", "3014123484936842", "3014123484955842", "3014123486935842", "3014123494935842", "3014123684935842", "3014124484935842", "3014143484935842", "3014223484935842" }

  26. "3014080000000008"

    Returns: { "3014000000000008", "3014080000000000", "3014080000000018", "3014080000000208", "3014080000001008", "3014080000020008", "3014080000100008", "3014080002000008", "3014080010000008", "3014080200000008", "3014081000000008", "3014180000000008" }

  27. "0000000000000008"

    Returns: { }

  28. "3014133451234555"

    Returns: { "3014133415234555", "3014133431234555", "3014133451234055", "3014133451234535", "3014133451234550", "3014133451236555", "3014133451284555", "3014133451934555", "3014133456234555", "3014133951234555", "3014135451234555", "3014183451234555", "3014833451234555" }

  29. "3014123451234555"

    Returns: { "3014121451234555", "3014123051234555", "3014123451034555", "3014123451232555", "3014123451234155", "3014123451234551", "3014123451234585", "3014123451294555", "3014123457234555", "3014123481234555", "3014183451234555", "3014423451234555" }

  30. "3014000000000008"

    Returns: { "3014000000000008" }

  31. "3041123456789013"

    Returns: { "3014123456789013" }

  32. "3014400000000000"

    Returns: { "3014400000000000" }

  33. "3014111111111210"

    Returns: { "3014111111111210" }

  34. "3014123451284555"

    Returns: { "3014123411284555", "3014123451284515", "3014123451284556", "3014123451284655", "3014123451289555", "3014123451294555", "3014123451784555", "3014123452284555", "3014123551284555", "3014124351284555", "3014128451284555", "3014133451284555", "3014213451284555", "3014623451284555" }

  35. "3014123456789031"

    Returns: { "3014023456789031", "3014103456789031", "3014122456789031", "3014123256789031", "3014123454789031", "3014123456689031", "3014123456769031", "3014123456788031", "3014123456789013", "3014123456789021", "3014123456789039", "3014123456789831", "3014123496789031", "3014123546789031" }

  36. "2014123456789012"

    Returns: { }

  37. "3014080000000000"

    Returns: { "3014080000000000" }

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: