TopCoder problem "HammingNumbers" used in SRM 236 (Division I Level Two)



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

0)
    
{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.
1)
    
{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.
2)
    
{7,9,14,6}
52
Returns: 4802
3)
    
{4,11,15,21,29,28}
2841
Returns: 2146636800
Watch out for overflow. This is the last number before we have to return -1.
4)
    
{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.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=4459

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=6535&pm=4459

Writer:

dimkadimon

Testers:

PabloGilberto , lbackstrom , brett1479

Problem categories:

Advanced Math, Search