Day 42: Competitive Programming Journal

Date: October 25, 2024.

Hello Everyone,

Today marks Day 42 of my competitive programming journey, and I'm excited to share what I've worked on.

What I Did Today:

I tackled two problems: Generate Pascal's Triangle up to n rows and Count the number of set bits in an integer (Bit Manipulation).

1. Generate Pascal's Triangle up to n rows:
Problem:
Generate the first n rows of Pascal's Triangle. Each element is formed by the sum of the two numbers directly above it.

Explanation:
Use dynamic programming to generate each row of the triangle.
Each element is derived from the previous row based on the formula: row[i] = row[i-1] * (n - i) / i.

Here's the implementation:

vector<vector<int>> generatePascalTriangle(int n) {
    vector<vector<int>> triangle;

    for (int i = 0; i < n; i++) {
        vector<int> row(i + 1, 1);

        for (int j = 1; j < i; j++) {
            row[j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
        }

        triangle.push_back(row);
    }

    return triangle;
}

2. Count the number of set bits in an integer (Bit Manipulation):

Problem:
Count the number of 1s (set bits) in the binary representation of an integer.

Explanation:

• Use bit manipulation techniques like shifting and bitwise AND.
• Iterate through each bit of the integer to count the set bits.

Here's the implementation:

int countSetBits(int n) {
    int count = 0;
    while (n > 0) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

Reflection:
Today's problems helped strengthen my understanding of Pascal's Triangle and bit manipulation techniques. Generating Pascal's Triangle used combinatorial logic, while counting set bits demonstrated efficient bit manipulation. Both problems are essential in understanding mathematical patterns and low-level bit operations.

Stay tuned for more updates, and feel free to share your thoughts and experiences!