1.
Introduction
2.
Problem Statement
2.1.
Input
2.2.
Output
3.
Approach 1
4.
Program
4.1.
Space Complexity
5.
Approach 2
6.
Program
6.1.
Time Complexity
6.2.
Space Complexity
7.
Key Takeaways
Last Updated: Mar 27, 2024

# Minimum Possible Integer After at Most K Adjacent Swaps On Digits

Ujjawal Gupta
0 upvote

## Introduction

Ninja is preparing for his interview with Coding ninjas. After solving tonnes of DS problems, he thought of solving some algorithmic problems as well. He always found binary search problems very easy. So, he started with a problem namely minimum possible integer after at most K adjacent swaps on digits, which has a very cool application of binary search. Unfortunately, he couldn’t solve the problem optimally, which lowered his confidence. Would you like to help him with the same?

## Problem Statement

Given an integer ‘K’ and a string, ‘NUM’ represents the digits of a very large integer. At most ‘K’ times, you can swap any two adjacent digits of the number. Your task is to return a string representing the smallest integer that can be obtained.

### Input

NUM = ”9876”, K = 4

### Output

“6897”

The swaps are as follows:

``“9876” -----> “8976” -----> “8967” -----> “8697” ----> “6897”``

Thus the output after four swaps is “6897”.

## 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!

Live masterclass