# Missing Related Problem Set

• Find the Duplicate Number
Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Solution 1:

``````class Solution {
public:
int findDuplicate(vector<int>& nums) {
int low = 1;
int high = nums.size();
int mid = 0, count = 0;
while (low < high) {
mid = (low + high) / 2;
count = 0;
for(auto num : nums)
if (num <= mid)  count++;
if (count <= mid)
low = mid + 1;
else
high = mid;
}
return low;
}
};
``````

Detect cycle start point Method

``````class Solution {
public:
int findDuplicate(vector<int>& nums) {
if (nums.size() > 1) {
int slow = nums[0];
int fast = nums[nums[0]];
while (slow != fast) {
slow = nums[slow];
fast = nums[nums[fast]];
}
fast = 0;
while (fast != slow) {
fast = nums[fast];
slow = nums[slow];
}
return slow;
}
return -1;
}
};
``````

Missing Number

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

``````class Solution {
public:
int missingNumber(vector<int>& nums) {
//[left, right)
int left = 0, right = nums.size();
int cnt = 0;
while (left < right) {
int mid = left + (right-left)/2;
cnt = 0;
for (auto num : nums) {
if (num <= mid) cnt++;
}
if (cnt == (mid+1)) left = mid + 1;
else right = mid;
}
return left;
}
};
``````

Find first missing number Positive Number

``````class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
for (int i = 0; i < n; i++)
while (nums[i] > 0 && nums[i] <= n && nums[nums[i]-1] != nums[i])
swap(nums[i], nums[nums[i]-1]);
for (int i = 0; i < n; i++) {
if (nums[i] != i + 1)
return i + 1;
}
return n + 1;
}
};
``````

Missing Ranges

Given a sorted integer array where the range of elements are [0, 99] inclusive, return its missing ranges.

``````class Solution {
vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) {
vector<string> ranges;
int next = lower;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] == next) {
next++;
continue;
}
ranges.push_back(get_range(next, nums[i]-1));
next = nums[i] + 1;
}
if (next <= upper) ranges.push_back(get_range(next, upper));
return ranges;
}

string get_range(const int lower, const int upper) {
if (lower == upper) {
} else {
}
}
};
``````

There is another related problem , Summary Ranges

``````class Solution {
public:
vector<string> summaryRanges(vector<int>& nums) {
vector<string> result;
int i = 0, n = nums.size();
while (i < n) {
int j = 1;
while (i + j < n && nums[i+j]-nums[i] == j) ++j;
result.push_back(j <= 1 ? to_string(nums[i]) : to_string(nums[i]) + "->" + to_string(nums[i + j - 1]));
i += j;
}
return result;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.