HammingNumbers | Topcoder Archive

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

```
{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}

Returns: 532287

Factors contain the first 50 primes.

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.