Day 31: Competitive Programming Journal

Date: September 26, 2024.
Hello Everyone,

Today marks Day 31 of my competitive programming journey, and I’m excited to share what I’ve learned.

What I Did Today:
I tackled two problems: Tower of Hanoi and Find the kth Permutation Sequence.

1. Tower of Hanoi Problem:

Problem:
Given three rods and n disks, the task is to move all the disks from the source rod to the destination rod using the helper rod while following the rules:

• Only one disk can be moved at a time.
• A larger disk cannot be placed on top of a smaller disk.

Explanation:
The problem is solved using recursion. The idea is:

• Move n−1 disks from the source to the helper rod.
• Move the largest disk to the destination rod.
• Finally, move the n−1 disks from the helper rod to the destination rod.

Here’s the implementation:

void towerOfHanoi(int n, char source, char helper, char destination) {
    if (n == 1) {
        cout << "Move disk 1 from " << source << " to " << destination << endl;
        return;
    }

    towerOfHanoi(n - 1, source, destination, helper);

    cout << "Move disk " << n << " from " << source << " to " << destination << endl;

    towerOfHanoi(n - 1, helper, source, destination);
}

2. Find the kth Permutation Sequence:

Problem:
Given n, the numbers from 1 to n, and k, find the k-th permutation sequence in lexicographical order.

Explanation:
We used backtracking to explore all permutations of numbers 1 to n until the k-th sequence is found.

Here’s the implementation:

void findKthPermutation(vector<int>& nums, int k, string& result) {
    if (nums.empty()) return;

    int n = nums.size();
    int fact = 1;  // Factorial of (n-1)
    for (int i = 1; i < n; i++) {
        fact *= i;
    }

    int index = (k - 1) / fact;
    result += to_string(nums[index]);
    nums.erase(nums.begin() + index);

    k = (k - 1) % fact + 1;
    findKthPermutation(nums, k, result);
}

string getPermutation(int n, int k) {
    vector<int> nums;
    for (int i = 1; i <= n; i++) nums.push_back(i);

    string result = "";
    findKthPermutation(nums, k, result);
    return result;
}

Reflection:
Today's problems were challenging yet satisfying to solve. The Tower of Hanoi is a classic recursion problem that highlights the power of breaking down a complex problem into smaller, manageable steps. The k-th permutation problem was a great exercise in understanding factorials and recursion.

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