GeeksForGeeks - POTD | GFG POTD Answer
کانال بسته
1 218
مشترکین
اطلاعاتی وجود ندارد24 ساعت
-97 روز
-5730 روز
آرشیو پست ها
22nd October : C++ Solution ☝🏼
—————————————————————
🙋🏻♂️Discussion ⁉️
Join ✅ @GFG_Answer
class Solution
{
public:
long long power(long long x,int y, int p)
{
long long res = 1; // Initialize result
while (y > 0)
{
// If y is odd, multiply x with result
if (y & 1)
res = (res * x) % p;
// y must be even now
y = y >> 1; // y = y/2
x = (x * x) % p;
}
return res;
}
// Returns n^(-1) mod p
long long modInverse(long long n,int p)
{
return power(n, p - 2, p);
}
long long numberOfPaths(int M, int N)
{
long long path = 1,mod=1e9+7;
for (long long i = N; i < (M + N - 1); i++) {
path = (path*i)%mod;
long long inv=modInverse(i-N+1,mod);
path = (path*inv)%mod;
}
return path;
}
};
21th October : C++ Solution ☝🏼
—————————————————————
🙋🏻♂️Discussion ⁉️
Join ✅ @GFG_Answer
⭐Get ₹100 FREE Cashback⭐
#define ll long long
class Solution
{
public:
long long sumOfDivisors(int N)
{
ll c=0;
for(int i=1;i<=N;i++)
c+=i*(N/i);
return c;
}
};
20th October : C++ Solution ☝🏼
—————————————————————
🙋🏻♂️Discussion ⁉️
Join ✅ @GFG_Answer
⭐Get ₹100 FREE Cashback⭐
class Solution {
public:
int isPossible(int N, int arr[]) {
long long sum=0;
for(int i=0; i
19th October : C++ Solution ☝🏼
—————————————————————
🙋🏻♂️Discussion ⁉️
Join ✅ @GFG_Answer
⭐Get ₹100 FREE Cashback⭐
class Solution
{
public:
//Function to find the level of node X.
int nodeLevel(int V, vector adj[], int X)
{
queue q;
vector vis(V, 0);
int level = 0;
q.push(0);
vis[0] = 1;
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
int adjnode = q.front();
q.pop();
if (adjnode == X) {
return level;
}
for (auto x : adj[adjnode]) {
if (!vis[x]) {
vis[x] = 1;
q.push(x);
}
}
}
level++;
}
return -1;
}
};
18th October : C++ Solution ☝🏼
—————————————————————
🙋🏻♂️Discussion ⁉️
Join ✅ @GFG_Answer
MOOCs - @MOOCsCourses
class Solution {
bool util(vector adj[],vector &vis,vector &st_vis,int u){
vis[u] = true;
st_vis[u] = true;
for(auto v:adj[u]){
if(!vis[v]){
if(util(adj,vis,st_vis,v))
return true;
}else{
if(st_vis[v])
return true;
}
}
st_vis[u] = false;
return false;
}
public:
vector eventualSafeNodes(int V, vector adj[]) {
vector vis(V,false),st_vis(V,false);
vector ans;
for(int i = 0;i < V; i++){
if(!vis[i]){
util(adj,vis,st_vis,i);
}
}
for(int i=0;i
⚡Want To Get ₹100 Cash FREE⚡
1. Install App From PLAY STORE
⭐ ( TAP THIS LINK ) ⭐
2. Buy Digital Gold For ₹1 Rupees.
3. Verify With PAN Number.
4. Get Cashback Of ₹100 Rupees Instantly To Your Bank Account.
✨🔰🔰🔰🔰🔰🔰🔰✨
✨🔰COURSES 🔰✨
✨🔰🔰🔰🔰🔰🔰🔰✨
1⃣ D0T \/\/ĒB D€V
2⃣ $upr€m€ DS∆
3⃣ P\/\/ W€B D€V
4⃣ ∆LPH∆ B@tch
5⃣ UDMY ∆NDR01D D€V
⚠️How To Access Link⚠️
✨SHARE WITH YOUR FRIENDS✨
✨🔰🔰🔰🔰🔰🔰🔰✨
✨🔰COURSES 🔰✨
✨🔰🔰🔰🔰🔰🔰🔰✨
1⃣ D0T \/\/ĒB D€V
2⃣ $upr€m€ DS∆
3⃣ P\/\/ W€B D€V
4⃣ ∆LPH∆ B@tch
5⃣ UDMY ∆NDR01D D€V
⚠️How To Access Link⚠️
✨SHARE WITH YOUR FRIENDS✨
17th October : C++ Solution ☝🏼
—————————————————————
🙋🏻♂️Discussion ⁉️
Join ✅ @GFG_Answer
MOOCs - @MOOCsCourses
class Solution{
public:
vector> transitiveClosure(int n, vector>& graph) {
for(int via = 0; via < n; via++)
for(int src = 0; src < n; src++)
for(int dest = 0; dest < n; dest++)
if(graph[src][via] && graph[via][dest] || src == dest)
graph[src][dest] = 1;
return graph;
}
};
16th October : C++ Solution ☝🏼
—————————————————————
🙋🏻♂️Discussion ⁉️
Join ✅ @GFG_Answer
MOOCs - @MOOCsCourses
class DisjointSet{
private:
vector<int>parent;
vector<int>rank;
vector<int>size;
int n;
public:
DisjointSet(int n){
this -> n = n;
parent.resize(n+1,0);
size.resize(n+1,1);
rank.resize(n+1,0);
for(int i = 0; i <= n; i++){
parent[i] = i;
}
}
int find_parent(int a){
if(parent[a] == a){
return a;
}
return parent[a] = find_parent(parent[a]);
}
void unionByRank(int a, int b){
int uP_a = find_parent(a);
int uP_b = find_parent(b);
if(uP_a == uP_b) return;
if(rank[uP_a] < rank[uP_b]){
parent[uP_a] = uP_b;
}else if(rank[uP_a] > rank[uP_b]){
parent[uP_b] = uP_a;
}else{
parent[uP_b] = uP_a;
rank[uP_a]++;
}
}
void unionBySize(int a, int b){
int uP_a = find_parent(a);
int uP_b = find_parent(b);
if(uP_a == uP_b) return;
if(size[uP_a] < size[uP_b]){
parent[uP_a] = uP_b;
size[uP_b] += size[uP_a];
}else{
parent[uP_b] = uP_a;
size[uP_a] += size[uP_b];
}
}
int getSize(int i){
return size[i];
}
};
class Solution
{
int n;
int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};
bool isSafe(int i, int j,vector<vector<int>>& grid){
if(i < 0 j < 0 i == n j == n grid[i][j] == 0){
return false;
}
return true;
}
int solve(DisjointSet &ds, int i, int j,vector<vector<int>>& grid){
set<int>s;
for(int a = 0; a < 4; a++){
int nI = i + dx[a];
int nJ = j + dy[a];
if(isSafe(nI,nJ,grid)){
s.insert(ds.find_parent(nI*n+nJ));
}
}
int sum = 1;
for(auto it:s){
sum += ds.getSize(it);
}
return sum;
}
public:
int largestIsland(vector<vector<int>>& grid)
{
n = grid.size();
DisjointSet ds(n*n);
vector<pair<int,int>> to_change;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(grid[i][j] == 1){
for(int a = 0; a < 4; a++){
int nI = i + dx[a];
int nJ = j + dy[a];
if(isSafe(nI,nJ,grid)){
if(ds.find_parent(i*n+j) != ds.find_parent(nI*n+nJ)){
ds.unionBySize(i*n+j,nI*n+nJ);
}
}
}
}else{
to_change.push_back({i,j});
}
}
}
int largestLandSize = 0;
for(int i = 0; i < n; i++){
largestLandSize = max(largestLandSize,ds.getSize(i));
}
for(auto it: to_change){
int i = it.first;
int j = it.second;
largestLandSize = max(largestLandSize,solve(ds,i,j,grid));
}
return largestLandSize;
}
};
‼️Those Who Only Collect GeekBits‼️
✨You'll Get 2 Geekbits✨
Go To This Link - WEEKLY
And Paste This Answer ⬇️⬇️
👉🏼On 1st Question (PYTHON)👈🏼
⚡Q. Negative Prefix⚡
15th October : C++ Solution ☝🏼
—————————————————————
🙋🏻♂️Discussion ⁉️
Join ✅ @GFG_Answer
MOOCs - @MOOCsCourses
