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!

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read full post →

Top comments (0)

Postmark Image

Speedy emails, satisfied customers

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up