Sunday, February 15, 2009

Hammin numbers II

One problem with the previous solution is the amount of duplicates we generate. For instance, starting from 2 we can generate 2x3=6. Starting from 3 we can generate 3x2=6. We need to remove these duplicates as soon as possible to avoid unneeded elements in H. A solution is to use set operations, which is "logarithmic in general, but amortized constant if t is inserted right after p". So the complexity of this solution is O(nlogn) in worst case, and O(n) in average since hamming numbers are sparse among large integers.

#include <set>
#include <iostream>
#include <limits.h>

int main(){

typedef unsigned long long num;
typedef std::set<num> Nums;
typedef std::set<num>::const_iterator Nums_iterator;
Nums nums;
Nums_iterator it;


for (it = nums.begin(); it != nums.end(); ++it){

nums.insert(nums.end(), *it*2);
nums.insert(nums.end(), *it*3);
nums.insert(nums.end(), *it*5);
std::cout << *it << std::endl;

No comments:

Post a Comment