Pasted

// Cyclic sort:
We are given an array containing n objects. Each object, when created, was assigned a unique number from the range 1 to n based on their creation sequence. This means that the object with sequence number 3 was created just before the object with sequence number 4.
 
Write a function to sort the objects in-place on their creation sequence number in O(n) and without using any extra space. For simplicity, let’s assume we are passed an integer array containing only the sequence numbers, though each number is actually an object.
 
class CyclicSort {
 public:
  static void sort(vector<int> &nums) {
    int i = 0;
    while (i < nums.size()) {
      int j = nums[i] - 1;
      if (nums[i] != nums[j]) {
        swap(nums, i, j);
      } else {
        i++;
      }
    }
  }
 private:
  static void swap(vector<int> &nums, int i, int j) {
    int k = nums[i];
    nums[i] = nums[j];
    nums[j] = k;
  }
};
 
 
// Find missing number ranging [0, n] in an n sized array.
class MissingNumber {
 public:
  static int findMissingNumber(vector<int> &nums) {
    int i = 0;
    while (i < nums.size()) {
      if (nums[i] < nums.size() && nums[i] != nums[nums[i]]) {
        swap(nums, i, nums[i]);
      } else {
        i++;
      }
    }
    for (int i = 0; i < nums.size(); i++) {
      if (i != nums[i]) {
        return i;
      }
    }
    return nums.size();
  }
 
 
// We are given an unsorted array containing numbers taken from the range 1 to ‘n’. The array can have duplicates, which means some numbers will be missing. Find all those missing numbers.
 
 
class AllMissingNumbers {
 public:
  static vector<int> findNumbers(vector<int> &nums) {
    vector<int> missingNumbers;
    int i = 0;
    // [2, 3, 1, 8, 2, 3, 5, 1]
    // [3, 2, 1, 8, 2, 3, 5, 1]
    // [1, 2, 3, 1, 2, 3, 5, 8]
    // [1, 2, 3, 1, 2, 3, 5, 8]
    // [1, 2, 3, 1, 2, 3, 5, 8]
    // [1, 2, 3, 1, 5, 3, 2, 8]
    while (i < nums.size()) {
      if (nums[i] != nums[nums[i] - 1]) {
        swap(nums, i, nums[i] - 1);
      } else {
        i++;
      }
    }
    for (int i = 0; i < nums.size(); i++) {
      if (nums[i] != i + 1) {
        missingNumbers.push_back(i + 1);
      }
    }
    return missingNumbers;
  }
 
 
// Find duplicate element in [1, n]
  static int findNumber(vector<int> &nums) {
    //[2,1,3,3,5,4]
    //[1, 2, 3, 3, 5, 4]
    //[1, 2, 3, 3, 5, 4]
    //[1, 2, 3, 3, 5, 4]
    int i = 0;
    while (i < nums.size()) {
      if (nums[i] != nums[nums[i] - 1]) {
        swap(nums, i, nums[i] - 1);
      } else if (nums[i] - 1 != i) {
        return nums[i];
      } else {
        i++;
      }
    }
    return -1;
  }
 
// Find all duplicates:
 
class FindAllDuplicate {
 public:
  static vector<int> findNumbers(vector<int> &nums) {
    int i = 0;
    while (i < nums.size()) {
      if (nums[i] != nums[nums[i] - 1]) {
        swap(nums, i, nums[i] - 1);
      } else {
        i++;
      }
    }
 
    vector<int> duplicateNumbers;
    for (i = 0; i < nums.size(); i++) {
      if (nums[i] != i + 1) {
        duplicateNumbers.push_back(nums[i]);
      }
    }
 
    return duplicateNumbers;
  }