Statistics

Problem Statement for "TCPhoneHome"

Problem Statement

Typically, telephone numbers are sequences of digits (0-9) that all have the same length. However, some prefixes may be reserved for special purposes. This limits the total number of possible full-length telephone numbers that are available for general use in the system.

As an example, in much of the United States and Canada the local telephone numbers are 7 digits long. However, dialing 1 starts a special sequence for long distance, dialing 0 connects to the operator, and dialing 911 connects to emergency services. Thus, there are fewer than the theoretical 10,000,000 possible valid telephone numbers.

You are given the int digits: the length of the standard telephone numbers in the system. You are also given a String[] specialPrefixes. Each element of specialPrefixes is a string of digits that defines one reserved prefix. Standard telephone numbers cannot start with any of the reserved prefixes.

Compute and return the number of different standard telephone numbers in the system.

Definition

Class:
TCPhoneHome
Method:
validNumbers
Parameters:
int, String[]
Returns:
long
Method signature:
long validNumbers(int digits, String[] specialPrefixes)
(be sure your method is public)

Constraints

  • digits will be between 1 and 17, inclusive.
  • specialPrefixes will contain beteween 0 and 50 elements, inclusive.
  • The length of each element of specialPrefixes will be between 1 and digits, inclusive.
  • Each character of each element of specialPrefixes will be a digit ('0'...'9').
  • No two elements of specialPrefixes will be the same.

Examples

  1. 7

    {"0", "1", "911"}

    Returns: 7990000

    The example from the problem statement.

  2. 10

    {"0", "1", "911"}

    Returns: 7990000000

    Same prefixes, longer numbers.

  3. 8

    {"1", "12", "123"}

    Returns: 90000000

    The sets of numbers reserved by different special prefixes may sometimes overlap. For example, in this case the net effect of these three special prefixes is that all numbers that start with "1" are reserved.

  4. 9

    {"12", "13", "14"}

    Returns: 970000000

  5. 17

    {}

    Returns: 100000000000000000

  6. 10

    {"116","068537","862981","31245894","32","48552413","8530987","70627","6575654353","21947804","8469131","5775856938","2","0","60590","0257012873","457","514635300","689","9641055187","30547","425190363","2554339","682523436","95","53415389","146826","2101","89599265","16886","03","90807794","7","3","9","07481","114197","06429300","728051850","74","972118949","02443846","319101092","180216797","203"}

    Returns: 4969767658

  7. 14

    {"817575480605","0186","899928586","6281723","2715311551770","489488","8988028888062","833678624","93","8922","503736","9377","718754","800265796","9855611210637","8404855","563","48715","5039180064","3943531","31137291","63495"}

    Returns: 98877668689870

  8. 1

    {"0","3","8","7","6","9","5","2"}

    Returns: 2

  9. 1

    {"0","1","2","3","4","5","6","7","8","9"}

    Returns: 0

  10. 13

    {"464225","3591764","628550937980","169","1117179","287491673507","434","63342","9065","3145862","197","13855237874","4640583","52310","95212494","147","83866","0022263542","9640385650594","6855","7","74056294","852117234529","64","6889354113565","26197218","20545675","923608","77","5","789774553587","5980","438072155380","1364256","22013463492","851071652","1620746172302","79","85104","45526709","62","48","7273","928","0277","908707411946"}

    Returns: 7646674588757

  11. 7

    {"093","0","3","726","73","39","01","34318","07855","4209678","61445","806532","8"}

    Returns: 6889899

  12. 12

    {"924369702200","25259","995","79","3","38","65975329","732","793280","84604163","6574645","50920","152600702327","99","3794","26873496","13844414638","2428254","613","39848768","42897","418155","92","80844290","155","687018239","10070702"}

    Returns: 866968748989

  13. 17

    {"977392277598422","591019474348328","986196259","20116488438","60208574457","855099650","7462799575","32699778416","62198","56350284687597285","80919","630199500528","724051","1929077807937696","7462","434357040499","6110127025","068523057459462","8575480250623461","53985263421116","9394504","5691","812741823023","10","91332305257","132","0952937071","26149455557","50758471","87315765436177801","75779250127860","64983369012138384","605107065537"}

    Returns: 98877888774597677

  14. 9

    {"103928","0675","0128432","43277","16266517","828109450","426843656","975158","590495861","8950","17254772","0","00167","198595","7723","761605789","2860","44844","2751322","86433243","05986","7088093","892486463","01784","8019","95860815","1856","407570","248","09649","7","1834"}

    Returns: 798475856

  15. 15

    {"218316019204","8561010","504111570697971","068976","9534","1236787141","4","48516413","03302","7467695732019","9","63438688832829","669395","8680","8631","317968","1","78366539350","03357474925","9512","9792283","91599271","3733832664","16130","37047500","3240980214901","755304","91848","016133009264404","914243912965415","1800525703","39853891796","624946568","0369346572","66","3326","9864248","310","78694845","512349625"}

    Returns: 688686877768788

  16. 11

    {"902275","01696557","5187","1234390","9062090619","4725024182","7788","888366115","356","631038873","882","63941117","52751","88941695749","15658455228","55895","527753931","7","2011017043","6","50495799","87230254248","98235","25221109","4353","821496144","05835125907","66513","0","07"}

    Returns: 69776887667

  17. 4

    {"768","85","031"}

    Returns: 9880

  18. 11

    {"41286294","5873043","3378853004","4","4986","88208000","96","4264725","5687589020","97455625677","44507","977271295","0198097","0607479182","30722"}

    Returns: 88998978869

  19. 6

    {"70","36","7","579","47","9061","03","2051","2874","79873","672","389","648152","2","402"}

    Returns: 765899

  20. 2

    {"04","77","26","23","5","14","45","24","66","3","65","15","99","1","86","52","96","6","8","7","0","12","9"}

    Returns: 16

  21. 13

    {"0","59140","7616916","1339","1458876005847","835","2864934641404","40980","36","461212","8963103641313","6015972","3455427802442","4013633","723976072579","17660860","78","150","509546","24418"}

    Returns: 8778676899986

  22. 17

    {"7392257547775476"}

    Returns: 99999999999999990

  23. 17

    {"657415","41678608","813","88447798767080","3998680","97906629571","80264666","860664193","982478621572","665363","02401094","21010266657734175","391145","673126912936023","9","156672267548","64","352439","6157040991439","0908","846386279884","1805252","655","6341351660397","086111711115","5641916237662","860517543453","0512978","0193704600","9484160710","06576","1478307511360","24949100699757","280","75537531","9561029670756188","6503923232702950","0128","27547291375","870502287925512","417500338","513299530","96089992409504","299784775615","039103570","501088591857956","3294","8332","074"}

    Returns: 88558565588457689

  24. 17

    {"114773990797933","5803856","678677459658","94","30449649862555054","00521224727426","00811702","80489469339440822","911346145","4300","5317342671979","998920184687","845038686","4806432491862","3795795969","2206838","24013","411856229659","07","5212","02818","3","1","569273","02","0817499","003392666918392","798","19128872","280245559814","5183006","9","1471805044","4","846680797394","766623977","7437603","176","6941","340786037","3171911915219","287750","2185275882482"}

    Returns: 57878748799678899

  25. 17

    {"57059252","56508","76010","6735132827324204","8956370079","61289590797933973","66221","1422","3","432115438","075001","39771","74007","26044360","82897","2551120","0572057047956030","3094688395848","1279860555","71916124471044","9819866273914","6854787","223694792251723","71181870708","666590696172480","536459767873","398692650","6539","494370433","3790803","43285","540510819","2733","486425575212","862539","2991351878069","04633907530","52296346359417","7061427","162006435159957","62324","2155379265","312333981326842","4518","354045374","591535","283331947015564","395828861707"}

    Returns: 89952667667777579

  26. 3

    {"411"}

    Returns: 999

    Sometimes a "prefix" is actually a full length phone number that is specially reserved for some reason.

  27. 10

    {"123", "1234", "1235" }

    Returns: 9990000000

  28. 8

    {"1", "12", "123" }

    Returns: 90000000

  29. 1

    { }

    Returns: 10

  30. 5

    {"1", "12", "13" }

    Returns: 90000

  31. 17

    {"00000000000000000" }

    Returns: 99999999999999999

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: