## Hamming's Problem

Hamming wants an efficient algorithm that generates the list, in ascending order, of all numbers of the form 2^{i}3

^{j}5

^{k}for

*i*,

*j*,

*k*at least 0. This list is called the

*Hamming sequence*. The list begins like this:

1 2 3 4 5 6 8 9 10 12 15 16 18 ...

#### Brute force technique:

Take the first number you haven't checked yet, divide it by 2's, 3's and 5's until you can't do that any more, and if you're left with 1, then the number should go on the list; otherwise throw it away and try the next number. So:- Is 19 on the list? No, because it's not divisible by 2, 3, or 5.
- Is 20 on the list? Yes, because after we divide it by 2, 2, and 5, we're left with 1.
- Is 21 on the list? No, because after we divide it by 3, we're left with 7, which isn't divisible by 2, 3, or 5.

#### Linear Solution:

The idea is that to calculate`a[i]`

, we can use `a[j]*2`

for some `j < i`

. But we also need to make sure that:1)

`a[j]*2 > a[i - 1]`

and 2)

`j`

is smallest possible.Then,

`a[i] = min(a[j]*2, a[k]*3, a[t]*5)`

#include <iostream> #include <algorithm> #include <vector> using namespace std; int main(void) { // get n from user unsigned n; cout <<"n: "; cin >>n; // list of ugly numbers vector <uint64_t> ugly; uint64_t x = 1; ugly.push_back(x); // index of next multiple unsigned i2 = 0, i3 = 0, i5 = 0; // value of next multiple uint64_t x2 = 2, x3 = 3, x5 = 5; // loop through ugly numbers for(unsigned a = 1; a < n; a++) { x = std::min(x2, std::min(x3,x5)); ugly.push_back(x); if (x == x2) { i2++; x2 = ugly[i2] * 2; } if (x == x3) { i3++; x3 = ugly[i3] * 3; } if (x == x5) { i5++; x5 = ugly[i5] * 5; } } // return last ugly number found cout << x << endl; return 0; }

## No comments:

## Post a Comment