Statistics

Problem Statement for "HammingNumbers"

Problem Statement

Hamming numbers were first introduced as an exercise by Richard W. Hamming, the creator of Hamming codes. By definition, a Hamming number is a positive number that can be factored as the product of some arbitrarily chosen factors. For example, if the chosen factors = {2,3,5} then 90 = 2*3*3*5 is a Hamming number, but 70 = 2*5*7 is not because it is also divisible by 7. Note that 1 is always a Hamming number no matter what the chosen factors are.

Given a int[] of the chosen factors and an int n, return the n-th smallest Hamming number that can be obtained with these factors. n is 1-based, so the first number occurs when n = 1. If the result is above 2147483647 (32 bit signed integer maximum) then return -1.

Definition

Class:
HammingNumbers
Method:
getNumber
Parameters:
int[], int
Returns:
int
Method signature:
int getNumber(int[] factors, int n)
(be sure your method is public)

Constraints

  • factors will contain between 1 and 50 elements inclusive.
  • Each element in factors will be between 2 and 300 inclusive.
  • n will be between 1 and 100000 inclusive.

Examples

  1. {2,3,5}

    15

    Returns: 24

    The first 15 Hamming numbers generated by factors 2, 3 and 5 are: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24.

  2. {2,2,2,4,4,4,8,8,8}

    11

    Returns: 1024

    These numbers are all powers of 2. Thus the 11th Hamming number must be 2^10 = 1024.

  3. {7,9,14,6}

    52

    Returns: 4802

  4. {4,11,15,21,29,28}

    2841

    Returns: 2146636800

    Watch out for overflow. This is the last number before we have to return -1.

  5. {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89, 97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179, 181,191,193,197,199,211,223,227,229}

    100000

    Returns: 532287

    Factors contain the first 50 primes.

  6. {127,119,194,265,281,42,79,97,220,171,74,104,99,46,259,132,179,126,88,9,156,280,118,139,166,276,46,222,266}

    34849

    Returns: 975813210

  7. {195,219,224,228,157,148,183,49,193,257,218,16}

    53742

    Returns: -1

  8. {17,285,75,67,19,50,152,150,178,121,153,50,126,104,179,74,160,47,214,268,74,194,295,107,238,38,28,232,285,253,136,185,224,174}

    26354

    Returns: 184208192

  9. {232,70,230,136,51,28,227,236,146,47,209,184,11,285,27,102,89,130}

    91429

    Returns: -1

  10. {46,217,90,90,155,31,41,295,261,13,274,111,281,20,68,93,111,264,202,88,285,180,56,258,65,242,164,141,245,248,56,215,73}

    1418

    Returns: 436480

  11. {265,19,129,109,73,185,237,53,103,135,240,106,215,266,191,72,272,182,63,171,86,296,82,7,275,227,153,258,257,76,7,271,150,274,164,217,42,27,87,290,263,238,267,222,147,3,148,68,161}

    79514

    Returns: 72886485

  12. {21,108,258,262,211,22,53,60,103,239,290,122}

    35059

    Returns: -1

  13. {192,48,203,194,46,76,31,30,26,165,188,122,245,171,153,18,54,207,84,266,180,182,262,155,286,279,248,42,70,106,220,81,215,276,101,75,185,60}

    7870

    Returns: 3636360

  14. {251,39,162,13,94,120,237,208,83,291,249,226,263,82,7,231,279,45,256,54,238,121,195,45,40,28,96,275,269,102,288,109,244,173,285}

    69394

    Returns: 623143521

  15. {271,256,38,297,293,106,69,45,100,86,251,272,34,136,129,38,239,150,249,188,229,159,273,272,156,149,268,120,165,149,216,70,173,177,115,168,143,288,141,231,132,206,284,275,169,81,230}

    71453

    Returns: 454989312

  16. {120,23,89,225,42,188,211,51,238,154,260,135,89,143,81,89,251,259,41,112,240,231,109,272,249,4,199,173,291,119,204,22,115,41,289,251,33,104}

    70556

    Returns: 445800996

  17. {215,130,24,222,125,99,253,240,120,269,237,50,246,95,292,14,215,205,166,8,182,65,94,64,106,277,138,128,5,38,138,85,17,32,289,192,88,260,280,227,130,82,26,157}

    79742

    Returns: 194457424

  18. {194,93,47,206,103,82,48,287,27,138,17,233,204,210,172,125,50,10,12,126,17,115,233,252,297,115,225,283,157,95,84,288,19,229,108,111,282,13,244}

    65123

    Returns: 147993318

  19. {60,294,234,204,92,60,99,284,236,173,262,270,213,3,69,158,109,96,10,90,281,224,198,126,235,237,143,135,160,131}

    30336

    Returns: 382153200

  20. {192,216,16,129,285,160,261,233,104,8,20,295,298,70,288,277,49,19,221}

    66311

    Returns: -1

  21. {296,138,233,118,219,169,66,235,139,171,266,175,184,206,50,44,272,34,274,264,29,124,44,73,190,112,244,208,249,22,126,87,296,236,166,297,201,142,19,6,178,74}

    40430

    Returns: 57438444

  22. {140,87,134,106,263,4,60,18,119,40,34,177,50,193,4,46,204,54,24,256,245,123,84,223,265,171,52,227,81,3,80,92,42,296,13,177,260,196,95,270,291,21}

    76514

    Returns: 98585550

  23. {273,251,130,44,185,188,110,18,84,83,8,203,291,244,168,111,161,270,272,247,169,201,170}

    96227

    Returns: -1

  24. {268,259,84,60,221,261,5,68,30,120,267,55,195,40,90,298,100,142,298,67,264,230,134}

    27552

    Returns: -1

  25. {292,8,277,182,39,145,187,237,290,230,198,231,70,68}

    57096

    Returns: -1

  26. {33,268,291,136,250,36,233,148,258,215,133,109,187,192,17,159,184,220,124,130,47,7,90,186,71,149,148,145,212,247,195,99,177,277,248,90,81,186,62,238}

    24615

    Returns: 39261500

  27. {178,170,164,65,142,189,239,5,144,170,15,285,272,120,150,89,57,189,167,294,66,109,81,101,79,194,185,202,85,121,32,189,200,61,248,124,268}

    31992

    Returns: 86658000

  28. {150,2,43,16,154,201,280,180,3,89,180,255,13,235,181,222,63,190,236,228,203,128,54,42,144,73}

    12950

    Returns: 7539840

  29. {295,43,155,189,266,206,155,19,212,124}

    96342

    Returns: -1

  30. {300,299,298,297,296,295}

    1

    Returns: 1

  31. {300,299,298,297,296,295}

    2

    Returns: 295

  32. {81,280,137,169,267,215}

    3

    Returns: 137

  33. {191,208,69,107,192,138,227,296,37,183}

    72083

    Returns: -1

  34. {139,178,4,77,93,198,163}

    74642

    Returns: -1

  35. {270,199,21,122,78,209,266,276,216}

    57864

    Returns: -1

  36. {88,133,185}

    59344

    Returns: -1

  37. {280,36,76,207,281,241,112}

    322

    Returns: 2137608063

    Boundary case

  38. {280,36,76,207,281,241,112}

    323

    Returns: -1

    see previous case

  39. {68,224,38,45,288,241,176,100,277}

    779

    Returns: 2138137600

    boundary case

  40. {68,224,38,45,288,241,176,100,277}

    780

    Returns: -1

    see previous case

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

    100000

    Returns: 3247398

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

    100000

    Returns: 7381125

  43. {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53, 6,10,14,22,26,34,46,58,62,74,82,86,94,106, 15,21,33,39,51,57,69,87,93,111,123,129,141,159, 35,55,65,85,95,115}

    100000

    Returns: 7381125

  44. {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229 }

    100000

    Returns: 532287

  45. {7, 9, 14, 6 }

    52

    Returns: 4802

  46. {4, 11, 15, 21, 29, 28 }

    2841

    Returns: 2146636800

  47. {144, 100, 300 }

    33

    Returns: -1

  48. {300 }

    100000

    Returns: -1

  49. {7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 231, 295, 300 }

    100000

    Returns: 12112947

  50. {5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5 }

    15

    Returns: -1

  51. {2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74 }

    30000

    Returns: 42750240

  52. {154 }

    6

    Returns: -1

  53. {4 }

    17

    Returns: -1

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: