DEV Community

Jatin Jayadev
Jatin Jayadev

Posted on • Edited on

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);
}
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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!

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more

Top comments (0)

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay