Missing Test Case - 1675. Minimize Deviation in Array #1577
Description
Your LeetCode username
hqztrue
Category of the bug
- Question
- [√ ] Solution
- Language
Description of the bug
Here's a testcase that can make lots of accepted solutions get Time Limit Exceeded.
Code you used for Submit/Run operation
class Solution {
public:
int minimumDeviation(vector<int>& nums) {
set<int>s;
for(int i=0;i<nums.size();i++){
s.insert(nums[i]%2==0?nums[i]:nums[i]*2);//insert even directly and odd with one time multiplication and it will become even.
}
int diff=*s.rbegin()-*s.begin();
while(*s.rbegin()%2==0){//run the loop untill difference is minimized
int x=*s.rbegin();
s.erase(x);
s.insert(x/2);
diff = min(diff,*s.rbegin()-*s.begin());
}
return diff;
}
};
- from https://leetcode.com/problems/minimize-deviation-in-array/discuss/955262/C%2B%2B-intuitions-and-flip
class Solution {
public:
int minimumDeviation(vector<int>& nums) {
int res = INT_MAX, min_n = INT_MAX;
priority_queue<int> pq;
for (auto n : nums) {
n = n % 2 ? n * 2 : n;
pq.push(n);
min_n = min(min_n, n);
}
while (pq.top() % 2 == 0) {
res = min(res, pq.top() - min_n);
min_n = min(min_n, pq.top() / 2);
pq.push(pq.top() / 2);
pq.pop();
}
return min(res, pq.top() - min_n);
}
};
class Solution {
public:
int minimumDeviation(vector<int>& nums) {
set<int> s; //Set is used to remove simlar elements and avoids TLE
for(int i=0; i<nums.size(); i++){
if(nums[i] %2 == 1)
s.insert(nums[i]*2);
// If a element is odd it is multiplied by 2 and added in set
else
s.insert(nums[i]);
}
//s.rbegin() points to the last element of the array
//s.begin() points to the first element of the array
//We are storing the deviation in res
int res = *s.rbegin() - *s.begin();
// We are iterating until the last element comes out to be odd
// We are updating res if we got any deviation less than the current Deviation
while (*s.rbegin() % 2 == 0) {
s.insert(*s.rbegin() / 2);
s.erase(*s.rbegin());
res = min(res, *s.rbegin() - *s.begin());
}
return res;
}
};
- from https://leetcode.com/problems/minimize-deviation-in-array/discuss/952852/C%2B%2B-priority-queue
static auto speedup = []() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
return nullptr;
}();
class Solution {
public:
int minimumDeviation(vector<int>& nums) {
priority_queue<int> pq;
int x, y;
int mn=INT_MAX;
for (int i:nums){
if (i&1) i*=2;
pq.push(i);
if (i<mn) mn=i;
}
int res=INT_MAX;
while (true){
x=pq.top();
pq.pop();
res=min(res, x-mn);
if (x&1) break;
x/=2;
pq.push(x);
if (x<mn) mn=x;
}
return res;
}
};
Language used for code
C++
Expected behavior
The above accepted solutions all get Time Limit Exceeded.
Screenshots
Additional context
The testcase is too large to be uploaded here, so I created a link to it: https://github.com/hqztrue/shared_materials/blob/master/tmp/LeetCode/1675.in