HammingNumbers
SRM 236 · 2005-04-02 · by dimkadimon
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
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.
{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,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.
{7,9,14,6}
52
Returns: 4802
{4,11,15,21,29,28}
2841
Returns: 2146636800
Watch out for overflow. This is the last number before we have to return -1.
{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.
{280,36,76,207,281,241,112}
322
Returns: 2137608063
Boundary case
{280,36,76,207,281,241,112}
323
Returns: -1
see previous case
{68,224,38,45,288,241,176,100,277}
779
Returns: 2138137600
boundary case
{68,224,38,45,288,241,176,100,277}
780
Returns: -1
see previous case
Submissions are judged against all 53 archived test cases, of which 9 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class HammingNumbers with a public method int getNumber(vector<int> factors, int n) · 53 test cases · 2 s / 256 MB per case