Statistics

Problem Statement for "GoodNumbers"

Problem Statement

You are given int[]s a, b and an int N. A positive integer x is called good if it satisfies "x is a multiple of a[i] but not a multiple of b[i]" for at least one i. Return the count of all good numbers between 1 and N, inclusive.

Definition

Class:
GoodNumbers
Method:
count
Parameters:
int[], int[], int
Returns:
int
Method signature:
int count(int[] a, int[] b, int N)
(be sure your method is public)

Constraints

  • N will be between 1 and 1,000,000,000, inclusive.
  • a will contain between 1 and 10 elements, inclusive.
  • a and b will contain the same number of elements.
  • Each element of a and b will be between 1 and N, inclusive.

Examples

  1. {4}

    {3}

    20

    Returns: 4

    4, 8, 12, 16 and 20 are multiples of 4, but 12 is a multiple of 3. Thus 4, 8, 16 and 20 are good numbers.

  2. {3,2}

    {2,3}

    9

    Returns: 5

    3 and 9 satisfy the condition for i=0. 2, 4 and 8 satisfy the condition for i=1. 2, 3, 4, 8 and 9 are good numbers.

  3. {5,15,5,15}

    {4,4,2,2}

    50

    Returns: 8

  4. {1}

    {1}

    1000

    Returns: 0

    No number satisfies the condition.

  5. {168120222,756,408,194,681,856,964,677,250,845}

    {809,652,204,532,420,10,640688057,55,174076738,318}

    1000000000

    Returns: 16328141

  6. {74}

    {931}

    999999808

    Returns: 13498995

  7. {879,710}

    {115438893,43}

    999999273

    Returns: 2511785

  8. {328,841,304}

    {710,561,100}

    999999988

    Returns: 7300921

  9. {336,827,268,704877634}

    {150,822,673,337}

    999999279

    Returns: 7740201

  10. {229,195,2,709,669}

    {44788639,531,723,550,802}

    999999486

    Returns: 505477863

  11. {409,934,982,14,815,537}

    {670,95,502,196,405,299}

    999999854

    Returns: 73248392

  12. {506,753,717,439,502,872,138}

    {178,295,610,746,636,143,969}

    999999189

    Returns: 15862809

  13. {589673558,9,969,531,963,366,853,822}

    {713,902,51726006,58,791,213111267,7,99}

    999999413

    Returns: 115182465

  14. {455,290,334949810,124,814,60935239,221,367,227}

    {364,845,543436551,624,386,273,248,497,624}

    999999096

    Returns: 25556484

  15. {969,916,535,12,153,296,397,816,34,398}

    {548,211,212,378,626,869,777,440,332,302}

    999999421

    Returns: 118728494

  16. {578134257,598,705,605925151,413,798,382,66,700,130}

    {484,608,323,177,225,360280841,284660919,684570286,899,134}

    999999526

    Returns: 32247821

  17. {179,358,879,820,134,721,634,32,590,878}

    {359,599777255,794014916,481,103670398,108,1,36,114,594}

    999999558

    Returns: 46244104

  18. {419,586,16,103,644,968,270,304,104,386}

    {460,931,133,604,921,9135232,171620204,939825160,259,677}

    999999361

    Returns: 86899142

  19. {781,833,550,250,311,984,473392090,651,230,747}

    {231,777,245,697,65,614056599,941,552,206,164780468}

    999999951

    Returns: 18786727

  20. {414,51519751,784,118,551,196,512,270438667,48762044,566}

    {556228743,353,142,633413926,128,788,626,518,843,975}

    999999275

    Returns: 21159223

  21. {221,240,306,254,167,305,73646453,721,581,353}

    {699,812,892,729,662,121,268317159,628,962854266,595}

    999999446

    Returns: 30222964

  22. {828,532,517,516,602,662,325,937,16,265963217}

    {974,721,170,828,729,385,950,47,667,521}

    999999534

    Returns: 74215995

  23. {211,212,519,935,768,819,826,29,35,241}

    {541,936,49,12,65,238,246,773471031,711,38}

    999999385

    Returns: 80126118

  24. {716,580,165,502,290,34,562165090,812535218,39,339}

    {322,497,789,988,236,685,785,668,616,977}

    999999300

    Returns: 68339355

  25. {97,89,23,13,83,71,7,89,29,53}

    {53,61,61,41,7,5,11,53,41,7}

    16808

    Returns: 5053

  26. {29,19,31,23,97,7,59,31,83,3}

    {41,61,31,23,11,97,11,79,61,83}

    474833170

    Returns: 242765855

  27. {37,31,73,7,59,71,19,3,7,23}

    {71,67,53,97,79,13,7,83,59,97}

    551901394

    Returns: 292453863

  28. {3,7,5,23,7,23,89,17,31,43}

    {53,47,43,37,2,71,53,71,11,3}

    685118025

    Returns: 417430463

  29. {73,13,11,3,89,43,89,13,19,5}

    {59,59,41,43,71,3,83,79,7,41}

    864546518

    Returns: 505068578

  30. {156818623,253751015,225716029,257071437,243548886,229234434,212225039,214073095,259618806,205868303}

    {159111530,192035333,179549086,168299310,241111833,206614473,231582262,251714606,259697372,251998956}

    999996808

    Returns: 39

  31. {292029114,253509971,312129948,358442994,473861102,348473092,455121976,429857362,389715450,244005246}

    {379183686,304884938,301373083,442630584,468471703,253574684,377530978,341238638,386445575,358173558}

    999990445

    Returns: 25

  32. {66784354,122137114,103476140,77759463,79928408,98125505,74464572,127245591,91852628,86549142}

    {71842628,67687279,118649236,91478954,127773020,95168298,71011626,107510487,102420460,121261290}

    999998246

    Returns: 106

  33. {261867738,351980076,320626273,294599603,244288660,379842203,247550810,348995396,347712505,223131090}

    {370785714,204881654,289209283,274919842,333328819,250022311,322228676,286697645,399790462,230496735}

    999999528

    Returns: 29

  34. {363942150,417959484,261242501,342105621,447159407,319966570,452645864,387813844,330074172,330089721}

    {491783769,416035425,410025225,300325740,381095330,419175315,435339880,424511556,461580514,364362530}

    999991516

    Returns: 24

  35. {665932572,558116436,901164338,608764520,716937234,743926950,744945916,463548394,707376033,673060674}

    {897477768,465354299,664099310,765197169,752176840,699154563,893345019,669171947,630097741,531853910}

    999990471

    Returns: 11

  36. {428330100,270958791,260771890,387797564,417919525,338319786,294706606,316531041,346304491,399409431}

    {421748719,357689915,373488434,251287673,226894239,266886285,385989370,423832867,394722826,314597734}

    999999493

    Returns: 24

  37. {226029206,127590981,180598440,166458747,135342814,141566604,223220482,189169900,170195946,119885581}

    {178062987,204958540,157426970,233700760,167711689,156236311,157770294,220341594,200349135,204479132}

    999990970

    Returns: 58

  38. {66676660,110986572,61186678,83778706,73991869,114930795,72289929,72379363,92155870,64966605}

    {86834351,82187027,104826759,91744470,107977988,84001661,76696996,95766802,79094974,91402210}

    999991987

    Returns: 122

  39. {356728,466718,301622,523412,372198,506869,298129,457098,386105,428655}

    {393530,425537,296476,283556,266377,310245,312825,362378,473290,480194}

    999994508

    Returns: 25095

  40. {7,4,6,10,8,10,10,3,2,10}

    {8,10,2,4,9,9,9,3,8,3}

    999916808

    Returns: 568603487

  41. {6,8,8,2,10,9,9,4,7,3}

    {10,2,3,3,2,5,3,4,3,2}

    999917710

    Returns: 680896346

  42. {4,6,8,6,10,4,9,3,3,7}

    {5,10,5,6,9,9,2,10,10,3}

    999925486

    Returns: 588845008

  43. {8,9,6,9,9,9,8,6,7,2}

    {7,4,8,9,2,6,4,7,8,10}

    999940978

    Returns: 572585252

  44. {5,10,7,9,8,10,9,8,4,2}

    {5,2,4,7,4,10,3,2,5,5}

    999919452

    Returns: 535671136

  45. {7,8,5,7,9,9,10,10,2,3}

    {8,3,9,2,7,9,3,8,9,9}

    999921610

    Returns: 769384129

  46. {3,2,2,9,8,4,10,8,7,8}

    {3,4,7,6,10,9,10,3,8,5}

    999942083

    Returns: 618614964

  47. {9,7,3,8,2,4,4,10,2,3}

    {8,4,9,9,10,8,9,2,3,9}

    999983455

    Returns: 711496165

  48. {9,8,6,3,10,2,4,2,3,6}

    {6,9,7,4,3,5,8,4,9,7}

    999936551

    Returns: 666227567

  49. {5,9,10,4,8,2,9,7,7,3}

    {5,6,10,10,10,5,2,9,9,2}

    999954680

    Returns: 626955711

  50. {26611,41251,136793,197213,1435,23903,14413,13547,40061,7719}

    {77531,24541,53009,205757,15841,79591,483,252121,99619,34279}

    999016808

    Returns: 1104388

  51. {105,3703,46903,107113,3182,267173,2013,10439,11481,21983}

    {17405,125173,19671,6601,29465,5423,4526,526613,85157,31027}

    999728550

    Returns: 10819451

  52. {9503,132553,5795,236447,12561,13889,165731,5797,539251,69509}

    {18941,4539,134977,367993,5133,131279,7526,214223,156953,120931}

    999716396

    Returns: 629053

  53. {461287,110081,3538,2035,347261,255407,96347,48223,2542,4255}

    {2294,14673,278099,867,182683,17719,67469,11999,9503,345}

    999413497

    Returns: 1356575

  54. {70219,24153,2023,6674,4147,30349,182573,68,347189,44}

    {1353,15521,33019,30943,13363,140353,273,74399,10366,162781}

    999963250

    Returns: 36870990

  55. {349,589,186,955,674,190,163,957,830,721}

    {764,361,911,166,54,279,45,300,746,480}

    990016808

    Returns: 26137672

  56. {510,638,791,965,64,639,954,274,691,300}

    {118,218,921,156,947,167,12,796,849,776}

    994817710

    Returns: 30836894

  57. {13,888,422,483,685,103,837,894,957,421}

    {959,829,995,96,396,207,389,829,721,723}

    999125486

    Returns: 97193221

  58. {575,468,636,747,261,387,629,204,826,200}

    {403,328,620,585,740,429,931,484,719,775}

    991540978

    Returns: 24116776

  59. {473,604,61,234,431,118,540,278,373,92}

    {509,749,274,169,580,208,57,452,167,455}

    996319452

    Returns: 51744356

  60. {898,935,833,376,585,738,334,784,857,822}

    {44,588,171,821,250,252,867,557,648,54}

    991621610

    Returns: 15020575

  61. {129,290,956,855,908,580,109,611,250,530}

    {363,490,502,6,316,135,469,102,17,725}

    992842083

    Returns: 29408087

  62. {675,718,192,440,893,661,697,685,236,363}

    {35,139,117,558,235,215,504,407,606,936}

    995583455

    Returns: 21639181

  63. {117,692,735,498,208,299,49,92,372,735}

    {303,954,187,589,363,374,413,193,135,169}

    993436551

    Returns: 50244312

  64. {302,783,820,40,611,740,261,880,16,408}

    {284,843,748,901,262,581,65,171,180,668}

    993454680

    Returns: 84436448

  65. {970,920,365,489,141,488,527,729,204,775}

    {385,204,838,557,723,803,903,100,592,705}

    992737336

    Returns: 24476371

  66. {920,192,412,303,569,260,125,529,233,502}

    {767,803,317,691,770,12,340,195,256,887}

    994016856

    Returns: 31395290

  67. {759,309,989,374,113,401,244,970,475,170}

    {626,728,685,683,936,739,906,395,133,493}

    990687930

    Returns: 30746329

  68. {331,928,869,195,257,303,601,92,427,733}

    {467,641,721,771,855,10,728,392,355,542}

    993034749

    Returns: 32616799

  69. {404,107,265,538,841,437,853,282,151,785}

    {44,731,706,892,636,948,609,439,722,754}

    992883017

    Returns: 32542041

  70. {66301,53509,20373,15976,28556,65458,92512,57783,72677,49321}

    {2339,43786,9137,33880,96741,31896,87075,44049,53270,47919}

    900016808

    Returns: 231971

  71. {47733,82250,95075,94322,60751,10395,18648,24196,19150,30288}

    {39619,84683,94566,95394,57863,66668,17274,31774,16914,35516}

    964817710

    Returns: 334246

  72. {38794,13092,46052,95730,51463,31414,21816,63849,23385,75067}

    {98573,21475,29057,62205,47151,65502,39638,24877,18991,17463}

    999125486

    Returns: 302788

  73. {28583,76518,71052,47232,34587,27639,35243,99789,59272,55613}

    {55780,18211,41894,22788,75971,61287,65164,47716,45917,25984}

    971540978

    Returns: 215160

  74. {87197,27703,7045,57906,19448,49735,45567,48410,60223,62066}

    {63041,54947,90040,59659,14440,31636,70410,83108,33773,88610}

    946319452

    Returns: 334520

  75. {71656,63305,67055,84382,1575,84969,43318,93214,2216,79455}

    {41660,96906,16974,41213,39256,9684,74892,17783,16992,99369}

    951621610

    Returns: 1141756

  76. {39054,42149,96428,27882,86282,78061,61264,45350,26683,56240}

    {52734,28570,58687,22812,42751,87498,7939,56739,51803,79610}

    922842083

    Returns: 197044

  77. {15012,70747,62256,3374,41447,39739,54175,81136,35849,48459}

    {5381,90895,32715,49347,28045,34415,43344,22223,9372,67437}

    985583455

    Returns: 514008

  78. {25443,74726,4893,16932,12646,75548,13243,47009,28092,14406}

    {45996,909,38266,42835,48630,17474,77858,73462,66474,9601}

    943436551

    Returns: 575015

  79. {90041,92376,19,10894,5975,8030,24534,51082,24892,28290}

    {1940,29373,85276,36883,48331,45581,51005,88551,38691,1037}

    943454680

    Returns: 50128657

  80. {87946,4178,78089,7941,44214,3980,44843,75987,87468,19675}

    {31777,21975,23428,61037,56037,37595,36975,33823,34612,12900}

    902737336

    Returns: 686576

  81. {78806,38046,8134,66408,76790,15569,77858,87658,77417,55618}

    {35507,63821,59861,10348,941,15978,10645,54573,44041,31937}

    904016856

    Returns: 279586

  82. {48648,92847,78479,99896,67766,57875,12574,40039,36430,66698}

    {23333,54539,34624,31211,46143,1657,42675,3914,7747,65986}

    940687930

    Returns: 219196

  83. {72286,51499,95999,28518,99770,71007,55465,66791,85486,58954}

    {79253,72245,85006,43395,99009,93970,6614,73292,247,77132}

    993034749

    Returns: 163257

  84. {24533,52433,27454,9205,60259,73364,90430,25185,38302,39089}

    {92285,7697,99004,27379,26628,60114,13308,88828,87158,47842}

    902883017

    Returns: 304682

  85. {1,1,1,1,1,1,1,1,1,1}

    {2,3,4,5,6,7,8,9,10,11}

    1000000000

    Returns: 999963925

  86. {2,3,5,2,3,5,2,3,5,2}

    {3,5,2,5,2,3,2,3,5,3}

    987654321

    Returns: 691358025

  87. {2,3,5,7,2,3,5,7,2,3}

    {3,5,7,2,5,2,2,3,7,7}

    987654321

    Returns: 757201647

  88. {1,1,1,1,1,1,1,1,1,1}

    {1,1,1,1,1,1,1,1,1,1}

    1000000000

    Returns: 0

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: