• Welcome to Computer Association of SIUE - Forums.
 

Hard Question!!!

Started by Tony, 2007-11-19T15:07:50-06:00 (Monday)

Previous topic - Next topic

William Grim

#15
Answer to the previous question I posted under this topic:


#include <iostream>
#include <vector>
#include <cstdlib>

typedef std::vector<int> Integers;

const int MASK = 0x80000000;

void usage(const char *name_)
{
  std::cerr << "Usage: " << name_ << " <length>\n";
}

void printVector(const Integers &numbers_)
{
  using namespace std;
  for (unsigned i = 0; i < numbers_.size(); ++i) {
    cout << numbers_[i];
    if (i < numbers_.size()-1) {
      cout << ' ';
    }
  }
  cout << endl;
}

void printMissing(const Integers &numbers_) {
  using namespace std;
  for (unsigned i = 1; i < numbers_.size(); ++i) {
    if (!(numbers_[i] & MASK)) {
      cout << i;
      if (i < numbers_.size()-1) {
cout << ' ';
      }
    }
  }
  cout << '\n';
}

void findMissing(Integers &numbers_)
{
  for (unsigned i = 1; i < numbers_.size(); ++i) {
    int x = numbers_[i];
    if (x & MASK && x ^ MASK) {
      numbers_[x ^ MASK] |= MASK;
    }
    else if (x > 0) {
      numbers_[x] |= MASK;
    }
  }
}

/// @return Random number in range [min_, max_].
long boundedRandom(long min_, long max_)
{
  return random() % (1+max_-min_) + min_;
}

int main(int argc_, const char * const * argv_)
{
  using namespace std;

  if (argc_ < 2) {
    usage(argv_[0]);
    return -1;
  }

  srandomdev();

  unsigned length = atoi(argv_[1]);
  Integers numbers(length);

  for (unsigned i = 1; i < numbers.size(); ++i) {
    numbers[i] = (random() % 2) ? 0 : i;
  }

  for (unsigned i = 1; i < numbers.size()-1; ++i) {
    swap(numbers[i], numbers[boundedRandom(i+1, numbers.size()-1)]);
  }

  printVector(numbers);

  findMissing(numbers);
 
  printVector(numbers);
  printMissing(numbers);
 
  return 0;
}


Basically, to get around the problem of using separate data structures, you reuse the data structure given to you, which is an array.  You treat the upper-most bit in the numbers as the bit for your bitmap.  I'll let you read the code to learn the real magic, but if there are any questions, let me know.

P.S. Yes, I know my code is hard-wired for 32-bit numbers.  It's a demo, and so, I don't care.
William Grim
IT Associate, Morgan Stanley

Jerry

Just a quick glance it appears to be O(n), where n = the size of the original vector.

Can you prove it is O(1)?

"Make a Little Bird House in Your Soul" - TMBG...

William Grim

#17
Quote from: Jerry on 2007-12-04T15:13:26-06:00 (Tuesday)
Just a quick glance it appears to be O(n), where n = the size of the original vector.

Can you prove it is O(1)?



This problem requires O(N) space complexity.  The idea behind the problem is if you have terabytes or more of data, you had better not create a separate bitmap for the data.  Instead, reuse the resources you have if possible.

For the bitwise-XOR solution that solves a different problem, it is intrinsically O(1) space complexity.  The data structure used to solve the problem need not be O(N) space complexity.
William Grim
IT Associate, Morgan Stanley