Day 31: Competitive Programming Journal

Date: September 26,2024.
Hello Everyone,

Today is Day 31 of my competitive programming and I am excited to share what I have learned today.

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

1. Tower of Hanoi Problem:

Problem:
There are three rods and n disks. The objective of the problem is to move the disks from source rod to destination rod using helper rod under the given conditions:

• One disk can be moved at one time.
• A bigger disk cannot be placed on the top of a smaller one.

Explanation:

• Recursion is used to solve this problem. The approach is
• n-1 disks from the source rod must be moved to the helper rod.
• Now the largest disk has to be moved to the destination rod.
• Now, the n-1 disks must be moved from the helper rod to the destination rod.

Here is 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 explored all permutations of numbers 1 to n by backtracking until the k-th sequence was 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!