GEEKS FOR GEEKS SOLUTIONS🫢
Open in Telegram
1 342
Subscribers
No data24 hours
-27 days
-2930 days
Posts Archive
class Solution {
public:
int findMoves(int n, vector chairs, vector passengers) {
sort(chairs.begin(), chairs.end());
sort(passengers.begin(), passengers.end());
int ans=0;
for(int i=0;i
class Solution {
public:
bool isStraightHand(int n, int k, vector<int> &v) {
// k= group size
if(n%k>0){
return false;
}
map<int,int> mp;
for(auto it:v){
mp[it]++;
}
// put all the size() with its frquency in the (min)p_queue
priority_queue <pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>> > pq;
for(auto it:mp){
pq.push({it.first,it.second});
}
int cnt=0;
int last=-1;
queue<pair<int,int>> q;
while(pq.size()>0){
int t=pq.top().first;
int val=pq.top().second;
pq.pop();
// take top ele of the heap and check if the last element and
// the top element are coincidnt if not return false
// if yes then put the last ele to curr op element and move forward
if(val-1>0){
q.push({t,val-1});
}
// unit the group size is not reach dont re push the value of heap by subtracting one from it
// to pq again till then put the value in queue
cnt++;
if(last>=0){
if(t-last!=1){
return false;
}else{
last=t;
}
}
last=t;
if(cnt==k){
while(q.size()>0){
pq.push(q.front());
q.pop();
}
last=-1;
cnt=0;
}
}
// if int the end it finds that the value of cnt is not 0 means still some element left int group
if(cnt>0){
return false;
}
return true;
}
};
class Solution{
public:
static bool comp(vector< int> &a, vector &b)
{
if (a[1] == b[1])
return a[0] < b[0];
return a[1] < b[1];
}
vector kthSmallestNum(int n, vector> &range, int q, vector query)
{
// Write your code here
sort(range.begin(), range.end(), comp);
int index = 0, mini = range[0][0], maxi = range[0][1];
for (int i = 1; i < n; i++)
{
if (range[i][0] > range[i - 1][1])
{
range[index] = {mini, maxi};
index++;
mini = range[i][0];
maxi = range[i][1];
}
else
{
mini = min(mini, range[i][0]);
maxi = max(maxi, range[i][1]);
}
}
range[index] = {mini, maxi};
index++;
// cout< ans;
for (int i = 0; i < q; i++)
{
int num = query[i];
for (int j = 0; j < index; j++)
{
if (num <= range[j][1] - range[j][0]+1)
{
ans.push_back(range[j][0] + num-1);
num = 0;
break;
}
else
{
num -= range[j][1] - range[j][0]+1;
// cout< 0)
ans.push_back(-1);
}
return ans;
}
};
public:
void dfs(vector<vector<int>>& matrix, int r, int c) {
if (r < 0 r == matrix.size() c < 0 c == matrix[0].size() matrix[r][c] == 0) return;
matrix[r][c] = 0;
dfs(matrix, r + 1, c);
dfs(matrix, r - 1, c);
dfs(matrix, r, c + 1);
dfs(matrix, r, c - 1);
}
int closedIslands(vector<vector<int>>& matrix, int N, int M) {
for(int r = 0; r < N; r++) {
for(int c = 0; c < M; c++) {
if (r == 0 r == N - 1 c == 0 || c == M - 1) {
dfs(matrix, r, c);
}
}
}
int res = 0;
for(int r = 0; r < N; r++) {
for(int c = 0; c < M; c++) {
if (matrix[r][c] == 1) {
res++;
dfs(matrix, r, c);
}
}
}
return res;
}
class Solution {
public:
void dfs(vector<vector<int>>& matrix, int r, int c) {
if (r < 0 r == matrix.size() c < 0 c == matrix[0].size() matrix[r][c] == 0) return;
matrix[r][c] = 0;
dfs(matrix, r + 1, c);
dfs(matrix, r - 1, c);
dfs(matrix, r, c + 1);
dfs(matrix, r, c - 1);
}
int closedIslands(vector<vector<int>>& matrix, int N, int M) {
for(int r = 0; r < N; r++) {
for(int c = 0; c < M; c++) {
if (r == 0 r == N - 1 c == 0 || c == M - 1) {
dfs(matrix, r, c);
}
}
}
int res = 0;
for(int r = 0; r < N; r++) {
for(int c = 0; c < M; c++) {
if (matrix[r][c] == 1) {
res++;
dfs(matrix, r, c);
}
}
}
return res;
}
};
class Solution{
public:
int isPossible(int n, int m, string s){
// code hereint row=0;
int col=0;
int row=0;
int lm=0;
int rm=0;
int um=0;
int dm=0;
for(int i=0;i
class Solution{
public:
int dp[51];
bool isPowerOfFive(long long y){
if(y==1){
return true;
}
long long x=5;
long long expo=1;
while(expo=0;i--){
if(s[i]=='1'){
val+=pow(2,power);
}
if(isPowerOfFive(val)==true && s[i]!='0'){ // cannot have leading zeros
long long temp=helper(s,i-1);
if(temp!=INT_MAX){
res=min(res,1+temp);
}
}
power++;
}
return dp[curr]=res;
}
int cuts(string s){
memset(dp,-1,sizeof(dp));
int res=helper(s,s.size()-1);
return res==INT_MAX ? -1 : res;
}
};
class Solution {
public:
long long countBits(long long N) {
if(N == 0){
return 0;
}
if(N == 1){
return 1;
}
vector<int> lut = {1, 2, 5, 13, 33, 81, 193, 449, 1025, 2305, 5121, 11265, 24577, 53249, 114689, 245761, 524289, 1114113, 2359297, 4980737, 10485761, 22020097, 46137345, 96468993, 201326593, 419430401, 872415233, 1811939329};
int count = 0;
int setCountRem = -1;
//Count set bits in N
for(int x = N; x; x>>=1){
setCountRem += x & 1;
}
for(int x = 0; N; N>>=1){
if((N & 1) == 1){
count += lut[x] + setCountRem*pow(2,x);
setCountRem--;
}
x++;
}
return count;
}
};
class Solution {
public:
long long findMaxSubsetSum(int N, vector &A) {
// code here
long long a = A[0],b = A[1] + max(0,A[0]);
for(long long c,i=2;i
