Approach
The idea is straightforward, generate all the possible permutations of the given number N.
Check for every permutation; if it is divisible by K or not.
If the current permutation is divisible by K, then count the minimum swaps to make the permutation from the given number. Else move to another permutation of the number.
Calculate the minimum of all of these count values. Finally, return the value of minimum adjacent swaps.
To generate all the possible permutations, we will use the next_permutation function.
Steps of algorithm
minimum_swaps():
- Convert the given number N to a string of characters using the to_string() function.
- Create a mnm_swaps = 0 variable to store the result.
- Sort the number string in non-decreasing order using the sort function.
- Iterate through all the permutations of the number string using the next_permutation.
- If the current permutation is divisible by K, count the minimum swaps required to make the permutation from the number string. Else move to the next greater permutation.
- Update the current minimum swaps in the mnm_swaps variable.
- Return the value of the mnm_swaps.
count_swaps():
- For the first and second strings, use pointers i and j, respectively. Set i and j to 0 to begin.
- Iterate over the first string and increment the value to j to find the position j where str1[j] = str2[i]. Continue swapping adjacent elements j and j – 1 and decrementing j until it equals i.
- Now the ith element of the first string is equal to the second string, increment the value of i.
- This technique will yield the minimum number of steps as there are no unnecessary swaps.
Below is the implementation of the above approach:
Implementation in C++
#include <bits/stdc++.h>
using namespace std;
int count_swaps(string str1, string str2, int size)
{
int i = 0, j = 0;
int swaps = 0;
while (i < size)
{
j = i;
while (str1[j] != str2[i])
{
j = j + 1;
}
while (i < j)
{
char tmp = str1[j];
str1[j] = str1[j - 1];
str1[j - 1] = tmp;
j = j - 1;
swaps = swaps + 1;
}
i = i + 1;
}
return swaps;
}
int minimum_swaps(int N, int K)
{
string num_str = to_string(N);
sort(num_str.begin(), num_str.end());
int mnm_swaps = INT_MAX;
do {
if (stoi(num_str) % K == 0)
mnm_swaps = min(mnm_swaps, count_swaps(to_string(N), num_str, num_str.length()));
} while (next_permutation(num_str.begin(), num_str.end()));
return mnm_swaps;
}
int main()
{
int N = 4350609;
int K = 100;
cout << minimum_swaps(N, K);
return 0;
}
Output:
3
Complexity Analysis
Time complexity: O((logN)!*(logN)^2)
Since we are using the next permutation function having a time complexity of O(d!*d) and for every permutation, we are checking the minimum number of swaps required which take O(d) time where d is the maximum number of digits in N.
So, the overall time complexity of the algorithm will be O(d!*d*d) -> O((d*log10)! *(d *log10)^2) -> O((log10^d)! * (log10^d)^2) -> O((logN)!*(logN)^2).
Space complexity: O(logN), as we are using a string of size d.
So, the space complexity of the algorithm -> O(d) -> O(d*log10) -> O(log10^d) = O(logN) where, d is the maximum number of digits in N and N is the given number.
Check out this problem - Maximum Product Subarray
Frequently Asked Questions
What is the use of the prev permutation function in C++?
The prev permutation() function in C++ is used to reorder the elements in the range [first, last) into the previous lexicographically ordered permutation. Each of several possible ways to order or arrange a set or number of things is defined as a permutation.
How to find the old permutations of a string?
The steps to find the previous permutation are as follows:
- Find the largest index i such that str[i – 1] > str[i].
- Find the largest index j where j >= i and str[j] = str[i – 1].
- Str[j] and str[i – 1] should be swapped.
- Reverse the sub-array starting at str[i].
What are the types of permutations?
Permutation can be divided into the following categories:
- Permutation in which repetition is prohibited.
- Permutation in which repetition is allowed.
- The permutation of non-distinct objects.
- Circular permutation.
How to calculate the factorial of a number?
The product of all positive integers less than or equal to a given positive integer is known as the factorial of that number. It is denoted by that integer and an exclamation point.
Factorial(n) = n! = n * (n-1) * (n-2) * (n-3) ……… * 1.
Conclusion
This article discussed the next_permutation function and the approach to finding the minimum adjacent swaps of the digits required to make N divisible by K using the next permutation function and its C++ code.
Want to brainstorm more? Go and check out these recommended articles:
What are you waiting for? Let's move towards practicing more questions:
Check out some of the amazing Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, etc. along with some Contests and Interview Experiences only on Coding Ninjas Studio.
Cheers!
Thank you for reading!
305+ registered