GeeksForGeeks - POTD | GFG POTD Answer
Closed channel
1 218
Subscribers
No data24 hours
-97 days
-5730 days
Posts Archive
class Solution {
public:
int distributeTicket(int n, int k) {
if(k >= n) return n;
int l=1,h=n;
bool front = true;
while(l
class Solution{
public:
// Function to insert element into the queue
void insert(queue &q, int k){
q.push(k);
}
int findFrequency(queue q, int k){// note we are not passing by reference
// Your code here
int ct=-1;
while(!q.empty()){
if(q.front()==k) ct++;
q.pop();
}
return ct+1;
}
};
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <cmath>
using namespace std;
class Solution {
public:
long long dp(int idx, int d, int m, vector<vector<long long>>& memo, const vector<int>& v, const unordered_map<int, int>& mn, const unordered_map<int, int>& mx) {
if (idx >= m)
return 0;
if (memo[idx][d] != -1)
return memo[idx][d];
int left = 0, right = 0;
if (idx != 0) {
left = mn.at(v[idx - 1]);
right = mx.at(v[idx - 1]);
}
if (d == 1)
swap(left, right);
long long ans = 1e18;
int ret1 = 0, ret2 = 0;
if (idx == v.size() - 1) {
ret1 = abs(mn.at(v[idx]));
ret2 = abs(mx.at(v[idx]));
}
ans = min(ans, dp(idx + 1, 0, m, memo, v, mn, mx) + abs(mx.at(v[idx]) - left) + (mx.at(v[idx]) - mn.at(v[idx])) + ret1);
ans = min(ans, dp(idx + 1, 1, m, memo, v, mn, mx) + abs(mn.at(v[idx]) - left) + (mx.at(v[idx]) - mn.at(v[idx])) + ret2);
return memo[idx][d] = ans;
}
long long minTime(int n, vector<int>& locations, vector<int>& types) {
vector<int> v;
unordered_map<int, int> mn, mx;
for (int i = 0; i < n; i++) {
if (mn.count(types[i]) == 0) {
mn[types[i]] = mx[types[i]] = locations[i];
v.push_back(types[i]);
} else {
mn[types[i]] = min(mn[types[i]], locations[i]);
mx[types[i]] = max(mx[types[i]], locations[i]);
}
}
int m = v.size();
sort(v.begin(), v.end());
vector<vector<long long>> memo(m + 5, vector<long long>(2, -1));
return dp(0, 0, m, memo, v, mn, mx);
}
};
class Solution {
public:
string longestPalin (string S) {
int n = S.size();
int anslen = 0;
string ans = "";
for(int i = 0; i=0 && r anslen){
anslen = r-l+1;
ans = S.substr(l, anslen);
}
l--;
r++;
}
//even length
l = i, r=i+1;
while(S[l] == S[r] && l>=0 && r anslen){
anslen = r-l+1;
ans = S.substr(l, anslen);
}
l--;
r++;
}
}
return ans;
}
};
class Solution {
public:
long long maxDiamonds(int A[], int N, int K) {
priority_queue<int, vector<int>> pq;
for(int i=0; i<N; i++){
pq.push(A[i]);
}
long long ans = 0;
while(K--){
int maxi = pq.top();
pq.pop();
ans+=maxi;
pq.push(maxi/2);
}
return ans;
}
};
class Solution{
public:
vector kLargest(int arr[], int n, int k) {
sort(arr,arr+n);
vector ans;
for(int i=n-1; i>=n-k;i--){
ans.push_back(arr[i]);
}
return ans;
}
};
class Solution{
public:
int cutRod(int price[], int n) {
vector dp(n+1, 0);
for(int i = 1; i<=n; i++)
for(int idx = 0; idx
class Solution{
public:
void update(int a[], int n, int updates[], int k)
{
for(int i = 0; i < k; i++)
a[updates[i]-1]++;
for(int i = 1; i < n; i++){
a[i] += a[i - 1];
}
}
};
class Solution
{
public:
void Rearrange(int arr[], int n)
{
vector v;
for(int i=0; i=0)v.push_back(arr[i]);
for(int i=0; i
class Solution
{
public:
vectorfind_permutation(string s)
{
vector v;
sort(s.begin(),s.end());
v.push_back(s);
string s1=s;
while(true)
{
next_permutation(s.begin(),s.end());
if(s==s1)
break;
v.push_back(s);
}
return v;
}
};
