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!
Top comments (0)