Home August | 2022 | POTD GFG
Post
Cancel

August | 2022 | POTD GFG

01 July | Egg Dropping Puzzle

You are given N identical eggs and you have access to a K-floored building from $1$ to $K$.

There exists a floor f where $0 <= f <= K$ such that any egg dropped at a floor higher than f will break, and any egg dropped at or below floor f will not break. There are few rules given below.

  • An egg that survives a fall can be used again.
  • A broken egg must be discarded.
  • The effect of a fall is the same for all eggs.
  • If the egg doesn’t break at a certain floor, it will not break at any floor below.
  • If the eggs breaks at a certain floor, it will break at any floor above.

Return the minimum number of moves that you need to determine with certainty what the value of f is.

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
    int eggDrop(int n, int k) 
    {
        vector<vector<int>> dp(n+1, vector<int>(k+1, 0));
    
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= k; j++) {
                
                if(i == 1)
                    dp[i][j] = j;
                else if(j == 1)
                    dp[i][j] = 1;
                else {
                int ans = INT_MAX;
                for(int pi = 0, ci = j-1; ci >= 0; ci--,pi++) 
                    ans = min(ans,max(dp[i][ci],dp[i-1][pi]));
                dp[i][j] = ans+1;
                }
            }
        }
        
        return dp[n][k];
    }

02 July | Delete nodes greater than k

Given a BST and a value k, the task is to delete the nodes having values greater than or equal to k.

DFS

1
2
3
4
5
6
7
8
9
10
11
12
    Node* deleteNode(Node* root, int k)
    {
        if(!root) return root;
        
        if(root->data >= k)
            return deleteNode(root->left, k);
            
        root->left = deleteNode(root->left, k);
        root->right = deleteNode(root->right, k);
            
        return root;
    }

03 July |

###

1

04 July |

###

1

05 July |

###

1

06 July |

###

1

07 July |

###

1

08 July |

###

1

09 July |

###

1

10 July |

###

1

11 July |

###

1

12 July |

###

1

13 July |

###

1

14 July |

###

1

15 July |

###

1

16 July |

###

1

17 July |

###

1

18 July |

###

1

19 July |

###

1

20 July |

###

1

21 July |

###

1

22 July |

###

1

23 July |

###

1

24 July |

###

1

25 July |

###

1

26 July |

###

1

27 July |

###

1

28 July |

###

1

29 July |

###

1

30 July |

###

1
This post is licensed under CC BY 4.0 by the author.

Setting up MacOS

August | 2022 | Leetcoding Challenge