Date: November 15, 2024
Hello Everyone,
Today marks Day 52 of my competitive programming journey. Here’s what I worked on today:
What I Did Today:
I tackled two problems: Find the number of ways to climb n stairs with 1 or 2 steps at a time (Recursion) and Determine if two rectangles overlap on a 2D plane.
1. Find the number of ways to climb n stairs with 1 or 2 steps at a time (Recursion):
Problem:
Given n stairs, find the number of ways to reach the top if you can take 1 or 2 steps at a time.
Explanation:
Use recursion, where the number of ways to reach the n-th step is the sum of the ways to reach the (n−1)-th and (n−2)-th steps.
Base cases:
- If n=0, there is 1 way to stay at the ground (do nothing).
- If n=1, there is only 1 way (1 step at a time).
Implementation:
int countWaysToClimbStairs(int n) {
if (n == 0) return 1;
if (n == 1) return 1;
return countWaysToClimbStairs(n - 1) + countWaysToClimbStairs(n - 2);
}
2. Determine if two rectangles overlap on a 2D plane:
Problem:
Given two rectangles on a 2D plane, determine if they overlap.
Explanation:
Two rectangles overlap if they have a common area.
Conditions to check for overlap:
- One rectangle is to the left of the other (i.e., right edge of one is left of the other’s left edge).
- One rectangle is above the other (i.e., bottom edge of one is above the other’s top edge).
Implementation:
struct Rectangle {
int x1, y1, x2, y2;
};
bool isOverlap(Rectangle r1, Rectangle r2) {
if (r1.x2 <= r2.x1 || r2.x2 <= r1.x1) return false;
if (r1.y2 <= r2.y1 || r2.y2 <= r1.y1) return false;
return true;
}
Reflection:
Today’s problems tested recursion and condition-checking. The climbing stairs problem with 1 or 2 steps was an insightful use of recursion, while the rectangle overlap problem required geometry-based checks and simple logical conditions. Both exercises improved my understanding of recursion and basic geometry.
Stay tuned for more updates, and happy coding!
Top comments (0)