LeetCode Daily Problem P2598 Maximum MEX After Operations

---

Timeline

Timeline

2025-10-16

init

Math

---

Problem:

P2598 Maximum after operations MEX

https://leetcode.cn/problems/smallest-missing-non-negative-integer-after-operations/description/?envType=daily-question&envId=2025-10-16

TLE

Use a min-heap to store the values of each number in nums after taking the absolute value and then the remainder modulo value. Then count starting from the minimum value. If the value popped from the min-heap equals the current number, push it back after adding value. Repeat this process until the heap is empty or a non-consecutive value appears. However, this O(n log n) approach will time out.

#include <vector>
#include <algorithm>
#include <queue>

using std::priority_queue;
using std::vector;

class Solution {
    public:
	int cel_div(int a, int b)
	{
		return (a + b - 1) / b;
	}
	int findSmallestInteger(vector<int> &nums, int value)
	{
		// First turn all negative numbers into positive numbers
		// Then turn all numbers into remainders modulo value

		int i;
		int n = nums.size();
		int top_value;
		int last_value;
		int count = 0;
		priority_queue<int, vector<int>, std::greater<int> > min_heap;

		for (i = 0; i < n; i++) {
			if (nums[i] < 0) {
				nums[i] += cel_div(-nums[i], value) * value;
			}
			nums[i] = nums[i] % value;
			min_heap.push(nums[i]);
		}

		last_value = -1;

		while (!min_heap.empty()) {
			top_value = min_heap.top();
			if (top_value == last_value) {
				min_heap.pop();
				min_heap.push(top_value + value);
				continue;
			}
			if (top_value != last_value + 1) {
				break;
			} else {
				last_value = top_value;
				min_heap.pop();
			}
		}

		return last_value + 1;
	}
};

int main()
{
	vector<int> vec = { 3, 0, 3, 2, 4, 2, 1, 1, 0, 4 };
	int value = 5;
	Solution s;
	s.findSmallestInteger(vec, value);
}

Mathematical optimization

All possible remainders modulo value form a complete set. Suppose there are group complete sets of all possible remainders modulo value, then the maximum MEX of the final array is at least$value \times group -1$After removing these complete sets of values from nums, among the remaining numbers, one of the possible remainders modulo value must be missing; find the smallest missing one and add$value \times group -1$That’s it. In terms of implementation, count the occurrences of each remainder, take the smallest count as group; the smallest count, of course, cannot be 0,

#include <vector>
#include <algorithm>
#include <climits>
#include <unordered_map>

using std::vector;
using std::unordered_map;

class Solution {
    public:
	int cel_div(int a, int b)
	{
		return (a + b - 1) / b;
	}
	int findSmallestInteger(vector<int> &nums, int value)
	{
		// First turn all negative numbers into positive numbers
		// Then turn all numbers into remainders modulo value

		int i;
		int n = nums.size();
		int group = INT_MAX;

		int res;

		unordered_map<int, int> umap;

		if (value == 1) {
			return n - 1;
		}

		for (i = 0; i < n; i++) {
			if (nums[i] < 0) {
				nums[i] += cel_div(-nums[i], value) * value;
			}
			nums[i] = nums[i] % value;
			umap[nums[i]]++;
		}

		for (i = 0; i < value; i++) {
			if (umap.count(i) == 0) {
				return i;
			}
		}

		for (auto &[num, count] : umap) {
			if (count < group) {
				group = count;
				res = num;
			} else if (count == group) {
				res = std::min(res, num);
			}
		}

		res += group * value - 1;

		return res;
	}
};

int main()
{
	vector<int> vec = { 3, 2, 3, 1, 0, 1, 4, 2, 3, 1, 4, 1, 3 };
	int value = 5;
	Solution s;
	s.findSmallestInteger(vec, value);
}