Statistics

Problem Statement for "Divisibility"

Problem Statement

Given a int[] a, return the number of integers between L and R, inclusive, that are divisible by at least one of the elements in a.

Definition

Class:
Divisibility
Method:
numDivisible
Parameters:
int, int, int[]
Returns:
int
Method signature:
int numDivisible(int L, int R, int[] a)
(be sure your method is public)

Constraints

  • L will be between 1 and 1000,000,000, inclusive.
  • R will be between L and 1000,000,000, inclusive.
  • a will contain between 1 and 18 elements, inclusive.
  • Each element of a will be between 1 and 1000,000,000, inclusive.

Examples

  1. 293

    784

    {1}

    Returns: 492

  2. 255

    734

    {2}

    Returns: 240

  3. 579000

    987654

    {1,2}

    Returns: 408655

  4. 1

    1000000000

    {2,3}

    Returns: 666666667

  5. 1

    1000000000

    {2,3,5}

    Returns: 733333334

  6. 1

    1000000000

    {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,49,53,59}

    Returns: 866219330

  7. 1956

    9013

    {307,419}

    Returns: 40

  8. 8636

    9586

    {5,367,487,463,167}

    Returns: 200

  9. 45

    9320

    {331,11,263}

    Returns: 901

  10. 2775

    3716

    {109,541,367,179,373}

    Returns: 20

  11. 5006

    5276

    {89}

    Returns: 3

  12. 3763

    7291

    {2,139,229}

    Returns: 1784

  13. 1511

    7710

    {503,331,227}

    Returns: 58

  14. 3265

    7317

    {479,257}

    Returns: 25

  15. 4014

    6707

    {31,5,191,233,373}

    Returns: 633

  16. 1190

    4705

    {23,167,439,19,47}

    Returns: 425

  17. 132099861

    896205951

    {401,997,953,131,311,647,823,11,233,307,137}

    Returns: 92071183

  18. 29523792

    614794872

    {619,641,61,401,547,977,821,311,241,449,359,233,73,971,113,479,293,787}

    Returns: 41457613

  19. 468884929

    747545899

    {139,389,997,883,317,353,43,613,911,409}

    Returns: 12697475

  20. 244081265

    440998363

    {577,563,349,401,919,383,673,769,773,659,149,131,761,353,29}

    Returns: 13647283

  21. 781321609

    978767535

    {479,71,859,293,367,709,43,947,349,131,139,701,967,79,241}

    Returns: 16396957

  22. 136611947

    842842918

    {487,37,13,947,977,463,409,919,139,491,43,193,461,787,5,211}

    Returns: 226443102

  23. 26183360

    593571254

    {281,293,727,887,547,17,499,509,937,271}

    Returns: 43978932

  24. 181391331

    366127331

    {311,727,47,839,317,823,631,521,89,317}

    Returns: 8389700

  25. 305226977

    867602751

    {503,499,953,619,353,811,887,137,433,37,229,919,241,293,571}

    Returns: 34702812

  26. 573631434

    744665832

    {257,73,367,607,103,673,947,541,563,127,23,863,607,449,907,181,389}

    Returns: 16733558

  27. 33386289

    692050545

    {449,293,809,911,937,491,17,569,523,479,59,313,677,197,863,43}

    Returns: 79732571

  28. 1

    203235253

    {593,281,313,347,37,281,983,839,331,719,617,131,571,547,811}

    Returns: 11733362

  29. 1

    691845672

    {661,977,269,751,823,491,23,79,443,457,317,563,461,829,733,577,929}

    Returns: 56366267

  30. 1

    730625184

    {607,859,229,541,911,593,313,587,607,881,997,953,709,449,173}

    Returns: 21138141

  31. 1

    781534199

    {877,373,521,241,11,317,359,17,557,47,151,839,463,97,5,241,311}

    Returns: 279111975

  32. 431545624

    656697209

    {4,6,9,13,13,4,12,12,16}

    Returns: 98142999

  33. 779079809

    959846254

    {8,10,7,3,4,12,15,12,10,9,5,3,11,16,14,4,8}

    Returns: 124423658

  34. 295261852

    900777793

    {10,11,5,16,14,3,8,5,13,6,7,9,3}

    Returns: 402265836

  35. 279164578

    926989897

    {15,9,8,9,8,12,16,12,16}

    Returns: 183550507

  36. 939048

    459249086

    {8,8,10,11,9,15,11,13,12,13,14,10,11}

    Returns: 215343142

  37. 322888734

    497589119

    {34087,41625217,10807,135683,206170409,929395,39380443,14023,42231017}

    Returns: 35235

  38. 534233339

    728536399

    {401205073,49606807,2546897,31303249,42024497,31911563,23913173,252953,675638}

    Returns: 1163

  39. 527093991

    920192931

    {135729829,43621,73537,298267,2098579,230803,18476917,130243,232481,61177,2257273,14393,61247,8885629,254701}

    Returns: 64203

  40. 538681111

    810120201

    {6662681,2034419,130139,155189,220817,56334599,29954159,15264941,11563,62092343,271961}

    Returns: 29750

  41. 411223102

    464058173

    {8201,78343,49111411,20833,1943,386,531973,3949717,6826951,232481,8251,74593}

    Returns: 181057

  42. 146145755

    228485318

    {17572889,12963413,16826561,25397,80131,50569,178729,58517,5499293,9185801,1927469,724193}

    Returns: 7963

  43. 366740911

    774991350

    {215956721,1298621,3055769,291611,50249,39751,6936887,101249,122257,365681,436567,44259077}

    Returns: 29728

  44. 23825187

    961817706

    {19729,250774987,10551187,22207,9943441,13603,12402343,16349647,196409,362963,266188033,546383,3158929,293582489,602218}

    Returns: 169986

  45. 40658250

    827362756

    {145583,74629637,1285501,1960783,113851,513554,572537,165094861,134329561,311357,38870231,368699}

    Returns: 20933

  46. 219715920

    236947596

    {2809,207313,3539489,121699,14417147,2483,262,70409,3505783,30858761,290557039,37405741,14174851,27820747,113507}

    Returns: 79352

  47. 300434931

    544804453

    {1299709,2750159,7368787,15485863,179424673,373587883,982451653,83,887,53}

    Returns: 7766773

  48. 406999271

    598719942

    {1299709,2750159,7368787,15485863,179424673,373587883,982451653,389,593,347,383,683,131,719}

    Returns: 3849563

  49. 336466518

    651592018

    {1299709,2750159,7368787,15485863,179424673,373587883,982451653,47,607,137,139}

    Returns: 11659880

  50. 241021930

    984306573

    {1299709,2750159,7368787,15485863,179424673,373587883,982451653,137,181,733,431,421,571,941,929,349}

    Returns: 18856384

  51. 757148

    167851001

    {2,3,4}

    Returns: 111395903

  52. 301413357

    336971125

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

    Returns: 27430278

  53. 160567226

    659598369

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

    Returns: 384966883

  54. 4890852

    391749388

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

    Returns: 312655899

  55. 26239573

    35766291

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

    Returns: 7699418

  56. 3582036

    3890652

    {6,12,18}

    Returns: 51437

  57. 1711192

    1776924

    {4,8,12,16,20,24}

    Returns: 16434

  58. 451130

    4212385

    {5,10,15,20,25,30,35,40,45}

    Returns: 752252

  59. 9091341

    18798771

    {10,20,30,40,50,60,70,80,90,100,110,120}

    Returns: 970743

  60. 1747960

    3419320

    {2,4,6,8,10,12,14,16,18,20,22,24,26,28,30}

    Returns: 835681

  61. 1

    1000000000

    {2, 3 }

    Returns: 666666667

  62. 1

    1000000000

    {198979, 1989709, 255, 1989, 1003, 103, 1988921, 19891129, 19881119, 971, 13579, 999, 132457, 918, 777, 666, 1313113, 12321 }

    Returns: 19708039

  63. 1

    100000000

    {118237324, 415181394, 737873235, 383528379, 588122516, 176776276, 969373175, 856974179, 772298687, 316382359, 223265326, 771111884, 647548821, 112736348, 336793537, 757456872, 542157198, 793775623 }

    Returns: 0

  64. 173

    999999999

    {4, 6, 11, 22, 123, 246 }

    Returns: 397634815

  65. 173

    999999999

    {4, 6, 11, 22 }

    Returns: 393939324

  66. 1

    1000000000

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

    Returns: 18

  67. 1

    1000000000

    {1000000000, 999999999, 100, 1000000000, 999999999, 1000000000, 1000000000, 999999998, 999999997, 999999996, 999999995, 100, 200 }

    Returns: 10000005

  68. 1

    10

    {2, 4 }

    Returns: 5

  69. 1

    1000000000

    {1000000000, 999999999, 2, 4, 5, 7, 999999998 }

    Returns: 657142858

  70. 1

    1000000000

    {5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 }

    Returns: 643699953

  71. 2134

    21343241

    {16785407, 433494437, 39916801, 479001599, 27644437, 16769023, 1046527, 209953, 331777, 472393, 629857, 746497, 786433, 839809, 995329, 333667, 269987, 374321 }

    Returns: 565

  72. 2134

    913432413

    {16785407, 433494437, 39916801, 479001599, 27644437, 16769023, 1046527, 209953, 331777, 472393, 629857, 746497, 786433, 839809, 995329, 333667, 269987, 374321 }

    Returns: 24472

  73. 5234

    1000000000

    {2, 3, 5, 7, 12131312, 3243239, 8999999, 273827, 3, 5, 7474, 7584, 8738, 12, 15, 20, 4, 66 }

    Returns: 771425467

  74. 545

    154545

    {999999999, 999999998, 65536, 65535, 65534 }

    Returns: 6

  75. 1

    999999999

    {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 47, 53, 57, 61, 67 }

    Returns: 865002014

  76. 1

    1

    {1, 1, 1 }

    Returns: 1

  77. 1

    1000000000

    {536870912, 387420489 }

    Returns: 3

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: