Statistics

Problem Statement for "BottlesOnShelf"

Problem Statement

There are N bottles on a shelf (numbered from 1 to N). Some little kids are playing football near the shelf. Sometimes it happens that their ball hits the shelf and every bottle with an index between left[i] and right[i], inclusive, that is also divisible by damage[i] falls on the ground and breaks.


Given N and the arrays left, right and damage. The ball has hit the shelf exactly M times, where M is the size of each of the three arrays. Count and return the number of bottles broken by the kids.

Definition

Class:
BottlesOnShelf
Method:
getNumBroken
Parameters:
int, int[], int[], int[]
Returns:
int
Method signature:
int getNumBroken(int N, int[] left, int[] right, int[] damage)
(be sure your method is public)

Constraints

  • N will be between 1 and 1,000,000,000, inclusive.
  • left, right and damage will each contain between 1 and 18 elements, inclusive.
  • left, right and damage will contain the same number of elements.
  • Each element of left and right will be between 1 and N, inclusive.
  • For each i, left[i] will be less than or equal to right[i].
  • Each element of damage will be between 1 and 42, inclusive.

Examples

  1. 6

    {1,4}

    {4,5}

    {4,2}

    Returns: 1

  2. 20

    {9,12}

    {12,17}

    {4,6}

    Returns: 1

  3. 20

    {9,12}

    {12,17}

    {2,3}

    Returns: 3

  4. 20

    {1,6,9,12,12}

    {6,9,12,18,15}

    {6,3,6,9,3}

    Returns: 5

  5. 100

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

    {100,100,100,100,100,100,100}

    {2,3,5,6,10,15,30}

    Returns: 74

  6. 5

    {1,2,3,4,5}

    {1,2,3,4,5}

    {1,2,3,4,5}

    Returns: 5

  7. 5

    {1,2,3,4,5}

    {1,2,3,4,5}

    {5,4,3,2,1}

    Returns: 3

  8. 1000000000

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

    {1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000}

    {2,3,6,5,10,15,30,7,14,21,42,35}

    Returns: 771428572

  9. 1000000000

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

    {1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000}

    {2,3,6,5,10,15,30,7,14,21,42,35,1}

    Returns: 1000000000

  10. 42

    {20,15,28,20,10,9,10,13,12,14,12,1,28,23,14,10,16,6}

    {39,35,31,31,28,31,14,14,13,32,27,37,38,24,30,13,20,20}

    {40,42,18,38,30,39,20,32,22,33,42,38,41,19,33,8,38,25}

    Returns: 0

  11. 42

    {17,16,2,23,6,35,9,9,6,5,3,36,1,9,12,12,5,1}

    {32,26,39,27,27,38,11,21,16,26,12,39,23,13,36,31,35,42}

    {37,42,40,32,32,8,35,31,30,27,19,28,39,32,37,42,42,1}

    Returns: 42

  12. 1000000000

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

    {1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000}

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

    Returns: 1000000000

  13. 1000000000

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

    {1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000}

    {2,3,5,7,11,13,17,19,23,29,31,37,41}

    Returns: 854906348

  14. 1000000000

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

    {1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000}

    {32,27,25,7,11,13,17,19,23,29,31,37,41}

    Returns: 512726882

  15. 1000000000

    {445511862,300680249,217887589,183074589,218527829,783446680,187390620,812791662,97866712,790787790,705908297,366215674,84382239}

    {553898765,439395745,659173278,363878429,413768078,961590503,842984661,856260473,882872082,938268985,780457002,738003552,165599966}

    {32,27,25,7,11,13,17,19,23,29,31,37,41}

    Returns: 161956804

  16. 1000000000

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

    {1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000}

    {32,27,25,7,11,13,17,19,23,29,31,37,41,32,27,25,7,11}

    Returns: 512726882

  17. 981823487

    {638029176,802304180,380801382,175948044,61913820,551706543,251265594,53753242,622094624,550767806,133546123,11431059,901358754}

    {928365795,893472146,760813034,830014118,319125244,920537226,648314301,292263008,639783830,642098365,911719077,54652913,931507642}

    {29,23,19,13,32,8,29,37,41,23,4,8,17}

    Returns: 283046378

  18. 996180255

    {163689230,41867057,538593532,350671360,376990263,54182462,846245185,250473035,355771560,319829756,153655700,306054283,114655089,505691468}

    {764674297,334815028,926306527,455169914,692961274,629063308,985680786,372016512,766243051,483234347,430488704,959917992,711709812,743484571}

    {7,41,37,2,9,41,16,32,13,7,3,29,27,25}

    Returns: 296046347

  19. 662978771

    {148176420,157445963,243687333,51126640,217278779,530281418,106807063,60612227,320512431,436943107,109184933,222488175,328679024,120521519,225996355,88125810,39338353}

    {638010525,484867957,299642758,174524224,436266569,589415594,342360950,531239432,347081946,611670474,650008844,303549252,635517984,525761344,657266077,409656256,123285106}

    {16,3,16,13,5,41,11,7,8,3,3,5,37,41,2,7,7}

    Returns: 397004134

  20. 419485564

    {76896116,381949946,178786733,97721290,317057751,197359939,120006994,190056888,11547100,131221819,1911460,97607023,125691382,204057491,236686245,157536195,8971595}

    {88568035,402263039,310535558,182723594,357565211,372119590,204747629,225521419,267368548,203661659,284432105,252801620,141513747,301536661,318530487,290120666,260057507}

    {29,11,8,3,3,19,2,31,23,32,27,7,37,4,31,16,37}

    Returns: 139047270

  21. 350604994

    {146694712,202197570,159721120,73697984,139167427}

    {186696149,317122138,231289218,302771633,159034162}

    {16,9,27,37,13}

    Returns: 23990187

  22. 329300559

    {29909215}

    {86005603}

    {31}

    Returns: 1809561

  23. 827850611

    {385430819,753332000,484852286,558955867,138063017,93352591,339885106,112640483,205855512,6280550,85693286,192541414,285122109,468654206,660568409}

    {386405638,824105476,729889666,680130506,377387836,418732372,810904048,231551819,277668982,95350732,247798704,366548866,817423502,494430613,804615076}

    {31,13,25,25,9,25,16,27,4,11,7,19,9,8,19}

    Returns: 183554284

  24. 738409546

    {185454376,484177889,358252250}

    {412408769,624088885,724740246}

    {8,7,5}

    Returns: 116302815

  25. 419755659

    {46415864,257083994,330678154,18278138,240457624,61650450,324017058,286835907,30246550,233299765,142522870,21218027,76114876,96179065,93394749}

    {224374547,300631242,345775266,123429846,299973334,327915016,358551568,322340127,174666748,413439661,170017353,153685649,147605426,403082754,130921481}

    {8,17,32,8,3,16,5,8,3,8,16,25,19,9,29}

    Returns: 137665185

  26. 144177033

    {23496651,58609030,7355825,24194220,16420657,14748413,3110268,67026039,37990404,18251488}

    {71018435,97078549,41301003,134483128,47265500,134516316,71038467,104024768,120072506,76996218}

    {2,5,16,8,27,4,16,13,37,27}

    Returns: 51811161

  27. 128327532

    {24141060}

    {104952976}

    {31}

    Returns: 2606836

  28. 672153572

    {149390164,347846557,399384855}

    {472044070,593502532,581481174}

    {5,36,14}

    Returns: 81968525

  29. 483970401

    {122084464,251100192,97992844,87487778,159371750,103488367,128489074,229447925,69350828,83977698,26972637,295651026}

    {271192618,480070511,118019505,350830276,432636755,258195898,405057254,421919553,465422411,322023839,328847619,437183446}

    {28,25,26,6,6,11,5,22,39,13,4,8}

    Returns: 185210129

  30. 204968821

    {180588685,74327431,68460055,138572857,39634466,25549220,35150634,79499938,10856617,43371628}

    {196461601,113418591,91301902,178393251,85772476,115835191,113484548,105240262,108238194,121857691}

    {34,1,27,15,41,4,23,12,39,41}

    Returns: 58495991

  31. 966030758

    {619372099,40903812,112107335,71860544,771079355,121468680,241654742,554634984,334197200,9180320,918851900,2364865,373493691}

    {722776566,540794183,122931539,81798097,842809302,659023326,490952154,695021786,900624564,386007867,937402115,115275077,469431192}

    {11,27,8,5,23,28,28,41,38,23,25,32,3}

    Returns: 115314320

  32. 55806634

    {9387559,2369258,8186449,48230704,28826563,39777577,7084035,10167148}

    {46996340,10088634,41018543,49866212,44943784,48826768,15039708,52834942}

    {17,2,20,28,12,42,12,36}

    Returns: 9574300

  33. 611994221

    {148564751,227890644,24759804,276458052,228412869,440511281,205286881,270883044,249891792,328170778,483758090,200454197,180415706,198041174,193934397}

    {341461465,278947332,298503239,416882428,366499567,448825257,367790170,474460058,257620855,475649063,562700490,600687381,587590804,350197067,395713170}

    {37,21,16,21,26,29,40,8,32,30,8,40,16,4,35}

    Returns: 97521062

  34. 490364441

    {370981620,200054457,168104327,249716040,306186631,192782098,100401657,190462549,200371356,267903341,82089426,215393279,140773942,98733268,151181154,48469735,38479984}

    {447814977,332337865,287677818,465352219,447619626,386778150,339456367,295972965,432084108,278894886,193403189,444396706,251393762,335879125,329847796,439951397,343363878}

    {11,25,36,14,4,3,37,23,40,40,7,12,27,38,32,28,6}

    Returns: 164254464

  35. 468071663

    {394455569,121244212,366062624,209560036,25764962,150128527,223794229,1346200,343824505,41153481,75734829,55886666,88184829,232506996,66588656,76113686,114425462}

    {458585015,227822900,449321208,389046045,370171514,163098841,228017176,462791961,352543093,158443966,336232064,314953921,423791528,430807747,173720462,114589922,404207188}

    {3,39,5,19,26,18,36,35,4,39,15,1,31,10,20,27,1}

    Returns: 375962471

  36. 742407338

    {247537384,296253362,49174021,606473428,355074936,48852992}

    {278302634,723202873,296919560,619810198,395048418,586604298}

    {26,21,16,20,42,40}

    Returns: 47455618

  37. 693023721

    {58277274,125397730,291502941,356101684,580468664}

    {65928298,139970546,306035801,508655304,655527718}

    {2,26,15,10,12}

    Returns: 26865146

  38. 988503863

    {129121222,167979298,188945458,257308892,389527916,525074004,615175260,751193173,880996540}

    {166764381,183390612,229126997,345674601,391543669,538267111,696797565,790190933,883250346}

    {4,31,17,30,42,2,30,5,4}

    Returns: 32945368

  39. 682154485

    {7223247,153323950,181521851,285153694,401395464,456537642,495258777,527314910,580293527}

    {21736128,154204817,182920065,387495589,450326837,456793582,507722820,538007043,663670680}

    {37,11,5,39,3,40,41,31,33}

    Returns: 22868457

  40. 795547527

    {11415007,45701768,111560128,130510564,147402455,247641276,342215523,354616150,436675063,474128501,497443001,536978890,616280777,640829911,765210947,776884473}

    {30970732,51980325,120131047,143941385,153888270,249770938,349607414,386816139,472355378,481695948,519712928,601244967,638394532,753163627,774643946,786623195}

    {10,10,5,14,33,19,6,10,14,17,23,26,7,15,14,33}

    Returns: 28068253

  41. 268504882

    {73931865,131183764,136369501,218513302}

    {103598577,135673650,203241074,229385976}

    {34,34,20,36}

    Returns: 4650203

  42. 420665939

    {6441892,28333696,38780796,85322530,117483831,130239120,133626197,146803787,153675552,157950298,188721854,217499277,219694154}

    {225033159,236942223,245823034,255155186,264054350,296006919,306267591,345047342,369285349,375910419,391807314,393515032,416980474}

    {23,16,31,38,16,8,1,12,36,37,42,30,37}

    Returns: 198437097

  43. 582486715

    {21449802,71676927,166940071,173827883,228230179}

    {549860311,423382608,398796130,318865569,297386410}

    {17,31,14,29,6}

    Returns: 69763067

  44. 566421763

    {20621108,41582618,134849847,154536750,174522956,176920589,208281771,218131892,233121452,259483136,273163912,283081705,290591369}

    {556432836,535717011,534270734,528595402,490259416,487470790,473364686,429625585,409682742,398424071,386830771,346299086,319875548}

    {36,1,39,7,28,26,41,7,7,30,24,31,13}

    Returns: 495292097

  45. 58222215

    {698635,1065326,10252157,10854957,11501953,15065886,16867554,17606381,18153580,20109972,21659416,22995391,25114075,27553835,27596130,27820452}

    {53711167,51791384,49799910,49160479,48886715,48388327,47905796,42301525,40351765,40069938,35842520,33910021,33470700,29897899,29251290,28833044}

    {34,19,21,29,18,27,10,20,34,5,17,16,32,22,14,42}

    Returns: 13808334

  46. 67782695

    {3163860,5079683,32221391}

    {42310157,56870405,61528223}

    {25,7,39}

    Returns: 9404079

  47. 816701166

    {289972998,392756528}

    {731229025,749156771}

    {22,13}

    Returns: 46289025

  48. 251895433

    {345255,10524436,17358277,19226625,34930634,50210874,109005374,118124562,119688854,126425955}

    {251821607,217595167,191568501,191321809,182759522,179090839,172354037,160256315,156473160,152712625}

    {9,38,2,37,30,5,34,33,37,32}

    Returns: 119682094

  49. 413809192

    {17624285,30865759}

    {204292173,111555647}

    {3,38}

    Returns: 63638242

  50. 907464483

    {64060951,134248804,150856644,245027915,373836681,487988935}

    {898151359,810315350,740577779,703756816,572832675,517406048}

    {13,35,38,21,25,17}

    Returns: 119144097

  51. 681768131

    {40585934,46174583,46448142,49498577,59277352,74186481,94449911,102919442,106447088,107961316,108304287,110113796,136267498,146114106,162801329}

    {678757476,650869547,623099425,617877051,557367458,545802393,500521372,465017604,416257921,360548921,321325141,301204987,300550230,289632947,260316486}

    {28,9,17,15,12,6,34,19,4,22,29,40,25,9,25}

    Returns: 239669066

  52. 7

    {1}

    {7}

    {2}

    Returns: 3

    Every second bottle has been broken by the kids. The shelf looks like this (.-unbroken, X-broken): .X.X.X.

  53. 7

    {1,1}

    {7,7}

    {2,3}

    Returns: 4

    Every bottle dividible by 2 or 3 has been broken. .XXX.X.

  54. 7

    {1,1,1}

    {7,7,7}

    {2,3,6}

    Returns: 4

    Now every bottle divisible by 6 has been broken also, but the result is the same as in last example. .XXX.X.

  55. 10

    {1,6}

    {5,10}

    {1,7}

    Returns: 6

    From the first half of the shelf, every bottle has been broken. From the second half only the bottle with number 7 has been broken. XXXXX.X...

  56. 5

    {4}

    {4}

    {7}

    Returns: 0

    None bottle has been broken.

  57. 1000000000

    {1}

    {1000000000}

    {1}

    Returns: 1000000000

    Every bottle has been broken.

  58. 1

    {1}

    {1}

    {1}

    Returns: 1

  59. 1

    {1,1,1,1,1}

    {1,1,1,1,1}

    {2,3,5,7,11}

    Returns: 0

  60. 2

    {1,1}

    {1,2}

    {2,2}

    Returns: 1

  61. 9

    {2,4,6}

    {4,6,9}

    {4,2,3}

    Returns: 3

  62. 9

    {2,4,6}

    {4,6,9}

    {4,5,3}

    Returns: 4

  63. 7

    {1, 1, 1 }

    {7, 7, 7 }

    {2, 3, 6 }

    Returns: 4

  64. 1000000000

    {1 }

    {1000000000 }

    {1 }

    Returns: 1000000000

  65. 1000000000

    {1, 3, 5, 7, 11, 13, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39 }

    {999999998, 999999994, 999999992, 999999988, 999999985, 999999982, 999999978, 999999975, 999999972, 999999968, 999999965, 999999962, 999999958, 999999955, 999999952, 999999948, 999999945, 999999942 }

    {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 36, 35, 34, 33, 32, 31 }

    Returns: 851278984

  66. 1000000000

    {1, 1, 1, 1 }

    {1000000000, 1000000000, 1000000000, 1000000000 }

    {2, 3, 5, 7 }

    Returns: 771428572

  67. 1000000000

    {1 }

    {1 }

    {2 }

    Returns: 0

  68. 1000000000

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18 }

    {1000000000, 999999999, 999999998, 999999997, 999999996, 999999995, 999999994, 999999993, 999999992, 999999991, 999999990, 999999989, 999999988, 999999987, 999999986, 999999985, 999999984, 999999983 }

    {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 4, 6, 8, 10, 12 }

    Returns: 854906348

  69. 999999999

    {1, 2, 3, 4, 5, 6, 16, 8, 9, 10, 11, 12, 13, 7, 9, 2, 5, 3 }

    {2, 3, 4, 5, 6, 16, 24, 9, 10, 11, 12, 13, 15, 9, 48, 5, 8, 8 }

    {41, 39, 2, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5 }

    Returns: 10

  70. 999999999

    {1, 1 }

    {500000000, 999999999 }

    {3, 5 }

    Returns: 333333332

  71. 1000000000

    {2, 5, 5, 6, 9, 8, 5 }

    {999999, 66666666, 52222222, 11111111, 444444, 21, 12 }

    {15, 21, 32, 21, 11, 21, 13 }

    Returns: 4819234

  72. 1000000000

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

    {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

    {42, 42, 42, 42, 42, 42, 42, 42, 42, 42 }

    Returns: 23809523

  73. 999999913

    {37, 2399, 4001, 35001 }

    {131313131, 313131313, 191919191, 919919911 }

    {36, 24, 40, 35 }

    Returns: 43470182

  74. 1000000000

    {1, 4 }

    {900000000, 900000999 }

    {2, 40 }

    Returns: 450000024

  75. 1000000000

    {1, 1, 1, 1, 1 }

    {1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

    {1, 1, 1, 1, 1 }

    Returns: 1000000000

  76. 1000000000

    {1, 1, 1 }

    {1000000000, 1000000000, 1000000000 }

    {2, 3, 5 }

    Returns: 733333334

  77. 1000000000

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

    {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

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

    Returns: 1000000000

  78. 1000000

    {1, 1 }

    {1000000, 1000000 }

    {1, 1 }

    Returns: 1000000

  79. 1000000000

    {1, 2 }

    {1000000000, 999999999 }

    {1, 1 }

    Returns: 1000000000

  80. 1000000000

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

    {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

    {2, 3, 6, 9, 41, 26, 39, 2, 3, 6, 9, 41, 26, 39, 23, 12, 22, 11 }

    Returns: 717214563

  81. 1000000000

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

    {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

    {2, 3, 5, 7, 11, 13, 17 }

    Returns: 819474645

  82. 1000000000

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

    {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

    {1, 2, 3, 4, 8, 13, 37, 31 }

    Returns: 1000000000

  83. 1251259

    {241874, 1011944, 731999, 600446, 438306, 1121082, 1029587, 934196, 217855, 1074761, 889022 }

    {760228, 1084694, 739779, 659932, 734588, 1140258, 1066362, 1247621, 678435, 1095779, 890713 }

    {1, 16, 23, 24, 26, 26, 7, 28, 19, 15, 3 }

    Returns: 541215

  84. 1000000000

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

    {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

    {2, 3, 4, 5, 7, 11, 13, 17, 23, 29 }

    Returns: 833277935

  85. 1000000000

    {1, 3, 5 }

    {1000000000, 999999999, 21321321 }

    {3, 5, 13 }

    Returns: 467541387

  86. 1000000000

    {1, 1, 1, 1 }

    {1000000000, 1000000000, 1000000000, 1000000000 }

    {2, 3, 6, 5 }

    Returns: 733333334

  87. 1000000000

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

    {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

    {41, 37, 31, 29, 27, 25, 23, 19, 17, 32, 13, 11 }

    Returns: 431514923

  88. 1000000000

    {1, 2, 3 }

    {1000000000, 99999999, 999999999 }

    {1, 39, 7 }

    Returns: 1000000000

  89. 1000000000

    {184862139, 378719191, 540507569, 321586011, 535506225, 14513834, 362448013, 756953209, 437113581, 318313193, 549160715, 106969295, 444106219, 85510009, 255275713, 381708720, 571692178, 79644360 }

    {705749206, 518080268, 660755588, 768076389, 991930745, 108442961, 364892845, 863334447, 571566238, 570831786, 566477303, 441999271, 992528670, 300354485, 632990439, 611357870, 919495772, 316675271 }

    {13, 26, 1, 2, 3, 38, 14, 21, 21, 17, 21, 24, 19, 12, 30, 38, 41, 34 }

    Returns: 446800710

  90. 1000000000

    {1, 480, 500, 1 }

    {499, 577, 520, 1000000000 }

    {2, 3, 4, 5 }

    Returns: 200000225

  91. 1000000000

    {1 }

    {1000000000 }

    {2 }

    Returns: 500000000

  92. 1000000000

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

    {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

    {37, 24, 33, 22, 21, 20, 19, 19, 17, 17, 19, 28, 11, 22, 41, 29, 29, 29 }

    Returns: 363222904

  93. 1000000000

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

    {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

    {2, 3, 5, 7, 9, 11, 13, 17, 19, 23, 27, 32, 31, 36, 38, 41, 42, 33 }

    Returns: 845550092

  94. 100

    {1, 1, 1, 1 }

    {60, 60, 60, 60 }

    {2, 5, 20, 22 }

    Returns: 36

  95. 10

    {1, 6 }

    {5, 10 }

    {1, 7 }

    Returns: 6

  96. 1000000000

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

    {73741824, 671088640, 512388096, 901086464, 684354560, 253635136, 805306368, 564423808, 181353841, 758096384, 227175424, 73741824, 503316480, 703877632, 497204736, 147483648, 288334336, 258143776 }

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18 }

    Returns: 606147090

  97. 1000000000

    {1, 2, 3, 4, 5, 1, 2, 3, 4, 5 }

    {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 999999999, 999999999, 999999999, 999999999, 999999999 }

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

    Returns: 1000000000

  98. 1000000000

    {1, 1 }

    {1000000000, 1000000000 }

    {2, 3 }

    Returns: 666666667

  99. 1000000000

    {1, 1, 1, 2, 2, 2, 3, 3, 3, 4 }

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

    {15, 4, 6, 5, 3, 2, 4, 7, 7, 5 }

    Returns: 9

  100. 1000000000

    {3, 3, 6, 8, 12, 14, 18, 20, 24, 30, 32, 38, 42 }

    {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

    {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41 }

    Returns: 854906336

  101. 999999999

    {101, 201, 301, 401 }

    {999000, 999000, 999000, 999999999 }

    {5, 15, 31, 39 }

    Returns: 25860785

  102. 1000000000

    {1, 2, 50, 71 }

    {999999999, 999888777, 555666888, 999999998 }

    {2, 3, 6, 12 }

    Returns: 666648129

  103. 1000000000

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

    {566544, 324422, 1212121, 222222, 332322, 21212111, 211, 21212, 444332, 323334, 333223, 223322 }

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

    Returns: 10697965

  104. 607684561

    {487731446, 315924757, 183490434, 532315133, 441589926, 580886130, 562544505, 327756867, 86496805, 280799339, 143005331, 523969601, 127371367, 473785134, 512675314 }

    {607300179, 607595521, 442884877, 561892924, 485806470, 588852789, 600468655, 334403302, 282393543, 311076650, 457688766, 528675645, 131592998, 596810622, 538887161 }

    {12, 25, 30, 36, 31, 21, 9, 32, 20, 20, 40, 32, 5, 26, 17 }

    Returns: 50751270

  105. 1000000000

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

    {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

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

    Returns: 1000000000

  106. 1000000000

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

    {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

    {5, 9, 17, 23, 3, 20 }

    Returns: 519863597

  107. 1000000000

    {1, 5, 100000, 700000, 10000, 20000 }

    {1000000000, 919542, 350000, 2100000, 28000, 42000 }

    {7, 3, 21, 21, 37, 33 }

    Returns: 143120146

  108. 999999999

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

    {999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999 }

    {1, 2, 3, 4, 1, 1, 1, 1 }

    Returns: 999999999

  109. 10000000

    {4, 5, 6, 7, 8 }

    {100000, 500000, 2000, 60000, 10000 }

    {2, 3, 6, 8, 16 }

    Returns: 199998

  110. 1000000000

    {1, 2, 3, 4, 5, 1, 6 }

    {1243, 1244, 12, 233, 344, 5, 12341244 }

    {2, 4, 6, 1, 42, 3, 2 }

    Returns: 6170738

  111. 1000000000

    {1000000000 }

    {1000000000 }

    {2 }

    Returns: 1

  112. 909090934

    {1, 4, 5, 7, 8, 9, 11, 13, 14, 15, 16, 13, 12, 12, 12, 11, 13, 13 }

    {24000, 23, 131, 1313, 3333, 42141421, 2441242, 21424124, 66666666, 909090934, 909090933, 909, 909, 909, 909, 909, 909, 909 }

    {1, 4, 2, 3, 3, 4, 4, 3, 5, 6, 23, 12, 11, 11, 14, 13, 13, 14 }

    Returns: 203197343

  113. 1000000000

    {1, 100, 200, 300, 400, 500, 600 }

    {100, 200, 300, 400, 500, 600, 700 }

    {7, 2, 4, 8, 16, 32, 3 }

    Returns: 146

  114. 1000000000

    {1 }

    {1000000000 }

    {41 }

    Returns: 24390243

  115. 100000000

    {1, 2, 2000, 1000, 2, 1 }

    {100000000, 10000000, 1000000, 100000, 10000, 1000 }

    {5, 10, 12, 15, 16, 32 }

    Returns: 20066900

  116. 10000

    {1, 1, 1, 1, 1 }

    {10000, 10000, 10000, 10000, 10000 }

    {8, 12, 16, 24, 30 }

    Returns: 1834

  117. 1000000000

    {1, 2, 50, 71, 2, 3 }

    {999999999, 999888777, 555666888, 999999998, 999999856, 999888633 }

    {2, 3, 6, 12, 7, 42 }

    Returns: 714269814

  118. 1000000000

    {1, 1, 1, 1, 1 }

    {1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

    {8, 12, 16, 24, 30 }

    Returns: 183333334

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: