Approach 1
This is a brute force approach. Here we are using recursion to find the solution. We observe that the number of swaps to reverse the entire string is (N * (N + 1)) / 2. Thus if ‘K’ is greater than (N * (N + 1)) / 2, then we can generate any permutation.
Thus we can generate the minimum number by sorting. Then we run a loop for all digits, one to ten and find the index of the smallest digit in the string. Then we put that number in the front and do it recursively for the rest of the string. We do this until K > 0. When K <= 0, we return the number.
Program
#include <iostream>
#include <string>
using namespace std;
string minInteger(string num, int k)
{
if (k <= 0)
return num;
int n = num.size();
/*
The total number of swaps to reverse the entire string is
(N * (N + 1)) / 2. If K > (N * (N + 1)) / 2, any order is achievable.
Thus, we can also find the minimum number by sorting it.
*/
if (k >= n * (n + 1) / 2)
{
sort(num.begin(), num.end());
return num;
}
// Starting from the smallest digit.
for (int i = 0; i < 10; i++)
{
// Find the index of smallest digit.
int idx = num.find(to_string(i));
// Checking if index is valid or not.
if (idx >= 0 && idx <= k)
// Moving the digit to the front and recursively repeating with rest of the string.
return num[idx] + minInteger(num.substr(0, idx) + num.substr(idx + 1), k - idx);
}
return num;
}
int main()
{
string num;
cin >> num;
int k;
cin >> k;
cout << minInteger(num, k) << endl;
return 0;
}
Input
9876
4
Output
6897
Time Complexity
O(N ^ 2 ), where ‘N’ is the length of the string.
Sorting takes O(Nlog(N)) whereas finding and inserting a digit takes O(N) each. This happens recursively so total time complexity is O(N^2) + O(Nlog(N)) = O(N^2).
Space Complexity
O(N), where N is the length of the string.
The recursive function will take O(N) space in the recursion call stack. Therefore, the space complexity is O(N).
Approach 2
The above problem can be solved greedily by traversing the string starting from the 0-th index and in each iteration taking the smallest integer in the range of remaining ‘K’ from that index and swapping it all the way left to the current index. After swapping, ‘K’ will be updated using BIT to store how many digits have been taken to the left of that digit.
When ‘K’ is 0, then all the remaining string is put back to the final string.
The implementation is shown below.
Program
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
vector<pair<int, int> > resort;
// Creating a min priority queue to store the index of each digit.
priority_queue<int, vector<int>, greater<int> > nums[10];
// Creating an array to store whether that index is used or not.
int used[30001];
int n;
int getSum(int index)
{
int sum = 0;
while (index > 0)
{
sum += used[index];
index -= index & (-index);
}
return sum;
}
// Update query in binary indexed tree.
void updateBIT(int index, int val)
{
while (index <= n)
{
used[index] += val;
index += index & (-index);
}
}
// Define Function minInteger().
string minInteger(string &num, int k)
{
// Initialize each element ‘used’ to 0.
for (int i = 0; i <= 3000; i++)
{
used[i] = 0;
}
int ctr = 0;
n = num.size();
// Inserting the index of each digit in the priority queue.
for (int i = 0; i < n; i++)
{
nums[num[i] - '0'].push(i + 1);
}
string res;
while (ctr < n && k > 0)
{
for (int i = 0; i <= 9; i++)
{
if (!nums[i].empty())
{
int cur = nums[i].top();
int holes = getSum(cur - 1);
int act = cur - holes;
if (act - 1 <= k)
{
res += ('0' + i);
k -= (act - 1);
updateBIT(cur, 1);
nums[i].pop();
break;
}
}
}
ctr++;
}
for (int i = 0; i <= 9; i++)
{
while (!nums[i].empty())
{
resort.emplace_back(nums[i].top(), i);
nums[i].pop();
}
}
sort(resort.begin(), resort.end());
for (auto &p : resort)
{
res += ('0' + p.second);
}
return res;
}
int main()
{
// Taking string as input.
string s;
cin >> s;
// Taking 'K' as input.
int k;
cin >> k;
// Function Call.
string ans = minInteger(s, k);
cout << ans;
}
Input
9876
4
Output
6897
Time Complexity
O(N * log(N)), where ‘N’ is the size of the string.
Traversing each index of string takes O(N) time and update query in BIT takes O(log(N)) time. So total time complexity is O(N*log(N)).
Space Complexity
O(N), where ‘N’ is the size of the string.
Here, creating an array ‘USED’ of size ‘N’ takes O(N) extra space. Therefore, it takes O(N) extra space.
Key Takeaways
In this blog, we learned about an interesting yet complex problem, namely Minimum Possible Integer After at Most K Adjacent Swaps On Digits. We have discussed the brute force approach which takes O(N^2) time. After that, we have discussed the optimised approach using BIT which takes O(Nlog(N)). To practice such challenging problems please head over to Coding Ninjas Studio. Stay tuned for such exciting problems.
Thanks, and Happy Coding!
305+ registered